// クエリ平方分割 + bitset の (N^1.5 + N^2 / 64) で満点を狙う。
#include <bits/stdc++.h>
using namespace std;
const int Backet = 700;
int N, M, A[200009], B[200009], X[200009], D1[200009], D2[200009], popcnt[1 << 22];
int num[200009], col[200009], colnum[200009], cnts, cntv;
bool used[200009], real_used[200009], vertex_used[200009], v[200009];
vector<int> G1[200009], G2[200009];
unsigned long long ptr[300009];
void init_state() {
for (int i = 1; i <= N; i++) { col[i] = 0; colnum[i] = 0; }
for (int i = 1; i <= N; i++) { vertex_used[i] = false; G1[i].clear(); G2[i].clear(); }
}
void dfs1(int pos) {
col[pos] = cnts;
for (int i : G1[pos]) { if (col[pos] == 0) dfs1(i); }
}
void dfs2(int pos, int rev) {
colnum[pos] = rev;
for (int i : G2[pos]) { if (colnum[pos] != rev) dfs2(i, rev); }
}
void solve(int l, int r) {
// 最初に、グラフに関係ない辺を貼り、連結成分ごとに分ける
cnts = 0; init_state();
for (int i = 1; i <= N - 1; i++) real_used[i] = used[i];
for (int i = l; i <= r; i++) { real_used[X[i]] = false; vertex_used[A[X[i]]] = true; vertex_used[B[X[i]]] = true; }
for (int i = 1; i <= N - 1; i++) { if (real_used[i] == true) { G1[A[i]].push_back(B[i]); G1[B[i]].push_back(A[i]); } }
for (int i = 1; i <= N; i++) { if (col[i] == 0 && vertex_used[i] == true) { cnts++; dfs1(i); } }
for (int i = 1; i <= N; i++) colnum[col[i]] = num[i];
//cout << "col = {"; for (int i = 1; i <= N; i++) { if (i >= 2) cout << ", "; cout << col[i]; } cout << "}" << endl;
//cout << "colnum = {"; for (int i = 1; i <= cnts; i++) { if (i >= 2) cout << ", "; cout << colnum[i]; } cout << "}" << endl;
// 次に、各クエリを処理する
for (int i = l; i <= r; i++) {
int pos = X[i];
if (used[pos] == false) {
// 連結する場合
int A1 = colnum[col[A[pos]]], A2 = colnum[col[B[pos]]];
for (int j = 1; j <= cnts; j++) { if (colnum[j] == A2) colnum[j] = A1; }
used[pos] = true; D1[i] = A1; D2[i] = A2; v[i] = false;
}
else if (used[pos] == true) {
// 分離する場合
used[pos] = false;
for (int j = 1; j <= cnts; j++) G2[j].clear();
for (int j = l; j <= i; j++) {
if (used[X[j]] == false) continue;
int p1 = col[A[X[j]]], p2 = col[B[X[j]]];
G2[p1].push_back(p2); G2[p2].push_back(p1);
}
int A1 = colnum[col[A[pos]]];
cntv++; dfs2(col[B[pos]], cntv);
D1[i] = A1; D2[i] = cntv; v[i] = true;
}
}
// 最後に、全体を更新する
for (int i = 1; i <= N; i++) { if (col[i] >= 1) num[i] = colnum[col[i]]; }
//for (int i = 1; i <= N; i++) cout << num[i] << " "; cout << endl;
}
void init() {
for (int i = 0; i < (1 << 22); i++) popcnt[i] = __builtin_popcount(i);
}
int ans[100009];
int main() {
//FILE *in = freopen("in1.txt", "r", stdin);
//FILE *out = freopen("out1.txt", "w", stdout);
int Q;
scanf("%d%d%d", &N, &M, &Q);
for (int i = 1; i <= N - 1; i++) {
scanf("%d%d", &A[i], &B[i]);
}
for (int i = 1; i <= M; i++) {
scanf("%d", &X[i]);
}
for (int i = 1; i <= N; i++) num[i] = i;
cntv = N;
// クエリ平方分割パート
for (int i = 1; i <= M; i += Backet) {
int L = i, R = i + Backet - 1; if (R > M) R = M;
solve(L, R);
}
//for (int i = 1; i <= N; i++) cout << i << ": D1 = " << D1[i] << ", D2 = " << D2[i] << endl;
// ビットセットパート
int BASE = 64; init();
for (int i = 1; i <= N; i += BASE) {
int L = i, R = i + (BASE - 1); if (R >= N) R = N;
for (int j = 1; j <= cntv; j++) ptr[j] = 0;
for (int j = L; j <= R; j++) ptr[j] += (1ULL << (j - L));
for (int j = 1; j <= M; j++) {
if (v[j] == false) ptr[D1[j]] |= ptr[D2[j]];
if (v[j] == true) ptr[D2[j]] = ptr[D1[j]];
}
for (int j = 1; j <= N; j++) {
unsigned long long E = ptr[num[j]];
ans[j] += popcnt[E & 4194303]; E >>= 22;
ans[j] += popcnt[E & 4194303]; E >>= 22;
ans[j] += popcnt[E];
}
}
for (int j = 1; j <= Q; j++) {
int cc;
scanf("%d", &cc);
printf("%d\n", ans[cc]);
}
return 0;
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &M, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[i]);
~~~~~^~~~~~~~~~~~~
synchronization.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &cc);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
26236 KB |
Output is correct |
| 2 |
Correct |
39 ms |
26232 KB |
Output is correct |
| 3 |
Correct |
41 ms |
26232 KB |
Output is correct |
| 4 |
Correct |
44 ms |
26232 KB |
Output is correct |
| 5 |
Incorrect |
39 ms |
26232 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1757 ms |
35952 KB |
Output is correct |
| 2 |
Correct |
1757 ms |
35828 KB |
Output is correct |
| 3 |
Incorrect |
1190 ms |
34160 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
26364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5109 ms |
36256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
26160 KB |
Output is correct |
| 2 |
Correct |
38 ms |
26220 KB |
Output is correct |
| 3 |
Correct |
38 ms |
26232 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
26232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
