2

More than 3 years have passed since last update.

posted at

Organization

# A - T or T

$N \times A$ と $B$ の小さい方が答えになります．

int main() {
int N, A, B;
cin >> N >> A >> B;
cout << min(N * A, B) << endl;
return 0;
}


# B - Good Distance

2点間の距離の二乗 $d$ が整数 $x$ の二乗と等しくなるかチェックします．

int main() {
int N, D, X[10][10];
cin >> N >> D;
for (int i = 0; i < N; i++) {
for (int j = 0; j < D; j++) {
cin >> X[i][j];
}
}
int res = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
int d = 0;
for (int k = 0; k < D; k++) {
d += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
}
int sq = sqrt(d);
for (int x = 0; x < sq + 1; x++) {
if (x * x == d) {
res++;
break;
}
}
}
}
cout << res << endl;
return 0;
}


# C - Remainder Minimization

$R - L \geq 2019$ のとき，$2019$ の倍数が必ず存在するため，最小値は $0$ になります．
$R - L < 2019$ のとき，$L \leq i < j \leq R$ にしたがって，$i, j$ を動かして最小値を求めます．

int main() {
long long L, R;
cin >> L >> R;
if (L % 2019 == 0 || R % 2019 == 0) {
cout << 0 << endl;
return 0;
} else if (R - L >= 2019) {
cout << 0 << endl;
return 0;
}
int res = 2018;
for (long long i = L; i < R; i++) {
for (long long j = i + 1; j <= R; j++) {
int r = i * j % 2019;
res = min(res, r);
}
}
cout << res << endl;
return 0;
}


# D - Rain Flows into Dams

\cfrac{X_{i}}{2} + \cfrac{X_{i + 1}}{2} = A_{i} \tag{1}


$i = 1$ から $i = N$ まで並べます．$X_{N + 1} = X_{1}$ としています．

X_{1} + X_{2} = 2 A_{1} \\
X_{2} + X_{3} = 2 A_{2} \\
X_{3} + X_{4} = 2 A_{3} \\
\cdots \\
X_{N} + X_{1} = 2 A_{N}


X_{1} = A_{1} - A_{2} + A_{3} - \cdots + A_{N}


int main() {
int N;
cin >> N;
vector<long long> A(N), res(N, 0);
for (int i = 0; i < N; i++) {
cin >> A[i];
if (i % 2 == 0) {
res[0] += A[i];
} else {
res[0] -= A[i];
}
}
for (int i = 1; i < N; i++) {
res[i] += A[i - 1] * 2 - res[i - 1];
}
for (int i = 0; i < N; i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}


# E - Virus Tree 2

const int MOD = 1000000007;
int N, K;
vector<vector<int>> G;

long long dfs(int curr, int prev) {
if (G[curr].size() > K) {
return 0;
}
int k = prev == -1 ? K - 1 : K - 2;
long long res = 1;
for (auto x : G[curr]) {
if (x == prev) {
continue;
}
res *= k;
res %= MOD;
k--;
}
for (auto x : G[curr]) {
if (x == prev) {
continue;
}
res *= dfs(x, curr);
res %= MOD;
}
return res;
}

int main() {
cin >> N >> K;
G = vector<vector<int>>(N);
for (int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
}
cout << dfs(0, -1) * K % MOD << endl;
return 0;
}


# F - Colorful Tree

まずは2頂点間の距離を求めます．

$u, v$ の共通祖先のうち根から最も遠い頂点(lca)を $w$ とすると，
$u$ と $v$ の距離は $d_{u} + d_{v} - 2 d_{w}$ で計算できます．

$u, v$ の深さを揃えてから，親が一致しない境界まで上に辿るとlcaが求められます．

struct node {
int to;
int col;
int dis;
};

struct query {
int id;
int col;
int dis;
int coef;
};

const int MAX_N = 100000;
const int MAX_LOGN = 20;
const int MAX_Q = 100000;
const int MAX_C = 100000 - 1;

vector<vector<node>> G(MAX_N);
vector<vector<query>> qs(MAX_N);

vector<vector<int>> par(MAX_N, vector<int>(MAX_LOGN, -1));
vector<int> dep(MAX_N, 0);
vector<int> dis(MAX_N, 0);
vector<int> cnt(MAX_C, 0);
vector<int> sum(MAX_C, 0);

vector<int> res(MAX_Q, 0);

void init(int u, int p = -1, int d = 0) {
if (p >= 0) {
par[u][0] = p;
dep[u] = dep[p] + 1;
dis[u] = dis[p] + d;
}
for (auto g : G[u]) {
int v = g.to;
if (v != p) {
init(v, u, g.dis);
}
}
}
void parent(int n) {
for (int i = 0; i < MAX_LOGN; i++) {
for (int j = 0; i < n; i++) {
if (par[j][i] != -1) {
par[j][i + 1] = par[par[j][i]][i];
}
}
}
}
int lca(int u, int v) {
if (dep[u] > dep[v]) {
swap(u, v);
}
for (int i = MAX_LOGN - 1; i >= 0; i--) {
if (((dep[v] - dep[u]) >> i) & 1) {
v = par[v][i];
}
}
if (u == v) {
return u;
}
for (int i = MAX_LOGN - 1; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}
void dfs(int u, int p = -1) {
for (auto q : qs[u]) {
int diff = q.dis * cnt[q.col] - sum[q.col];
res[q.id] += diff * q.coef;
}
for (auto g : G[u]) {
int v = g.to;
if (v == p) {
continue;
}
cnt[g.col]++;
sum[g.col] += g.dis;
dfs(v, u);
cnt[g.col]--;
sum[g.col] -= g.dis;
}
}

int main() {
int N, Q;
cin >> N >> Q;
for (int i = 0; i < N - 1; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
G[a].push_back({b, c, d});
G[b].push_back({a, c, d});
}
init(0);
parent(N);
for (int i = 0; i < Q; i++) {
int x, y, u, v;
cin >> x >> y >> u >> v;
u--, v--;
int w = lca(u, v);
qs[u].push_back({i, x, y, 1});
qs[v].push_back({i, x, y, 1});
qs[w].push_back({i, x, y, -2});
res[i] = dis[u] + dis[v] - 2 * dis[w];
}
dfs(0);
for (int i = 0; i < Q; i++) {
cout << res[i] << endl;
}
return 0;
}


Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
2