#include <bits/stdc++.h>
using namespace std;
#define NMAX 100010
int x[NMAX + 10], y[NMAX + 10];
int edge_active[NMAX + 10];
namespace AintP {
typedef struct Aint * Arbore;
typedef long long i64;
i64 rand_by_value[NMAX + 10];
struct Aint {
i64 hash = 0;
int suma = 0;
Arbore left = 0, right = 0;
void recalc() {
if (left)
hash ^= left->hash, suma += left->suma;
if (right)
hash ^= right->hash, suma += right->suma;
}
Aint() { }
Aint(int st, int dr, int poz) {
if (st == dr) {
hash = rand() | (rand() << 16);
suma = 1;
}
else {
int mij = (st + dr) / 2;
if (poz <= mij)
left = new Aint(st, mij, poz);
else
right = new Aint(mij + 1, dr, poz);
recalc();
}
}
};
Arbore unite(Arbore a, Arbore b)
{
if (!a)
return b;
if (!b)
return a;
if (a->hash == b->hash)
return a;
Arbore x = new Aint;
x->left = unite(a->left, b->left);
x->right = unite(a->right, b->right);
x->recalc();
return x;
}
}
AintP::Arbore vals[NMAX + 10];
namespace UF {
int tata[NMAX + 10];
int g[NMAX + 10];
vector <int> events;
int find(int x) {
if (g[x] == 0)
tata[x] = x, g[x] = 1;
while (tata[x] != x)
x = tata[x];
return x;
}
void unite(int a, int b) {
a = find(a);
b = find(b);
assert(a != b);
if (g[a] < g[b])
swap(a, b);
events.push_back(b);
g[a] += g[b], tata[b] = a;
vals[a] = AintP::unite(vals[a], vals[b]);
}
void undo() {
assert(!events.empty());
int node = events.back();
events.pop_back();
vals[node] = vals[tata[node]];
g[tata[node]] -= g[node];
tata[node] = node;
}
}
namespace Dynamic {
vector <int> aint[8 * NMAX + 10];
int l, r, val;
void update(int nod, int st, int dr) {
if (st > r || dr < l)
return;
if (l <= st && r >= dr) {
aint[nod].push_back(val);
return;
}
if (st != dr) {
update(2 * nod, st, (st + dr) / 2);
update(2 * nod + 1, (st + dr) / 2 + 1, dr);
}
}
void dfs(int nod, int st, int dr) {
for (auto i : aint[nod])
UF::unite(x[i], y[i]);
if (st != dr) {
dfs(2 * nod, st, (st + dr) / 2);
dfs(2 * nod + 1, (st + dr) / 2 + 1, dr);
}
for (auto i : aint[nod])
UF::undo();
}
}
int main()
{
ifstream cin("input.txt");
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; i++)
cin >> x[i] >> y[i];
for (int i = 1; i <= n; i++)
vals[i] = new AintP::Aint(1, n, i);
auto f = [m](int l, int r, int id) {
Dynamic::l = l;
Dynamic::r = r;
Dynamic::val = id;
Dynamic::update(1, 1, m);
edge_active[id] = 0;
};
for (int i = 1; i <= m; i++) {
int id;
cin >> id;
if (edge_active[id])
f(edge_active[id], i, id);
else
edge_active[id] = i;
}
for (int id = 1; id < n; id++)
if (edge_active[id])
f(edge_active[id], m, id);
Dynamic::dfs(1, 1, m);
while (q--) {
int id;
cin >> id;
cout << vals[id]->suma << '\n';
}
return 0;
}
Compilation message
synchronization.cpp: In function 'void Dynamic::dfs(int, int, int)':
synchronization.cpp:120:13: warning: unused variable 'i' [-Wunused-variable]
for (auto i : aint[nod])
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
38264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
38368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
38368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
38496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
38496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
