#include <bits/stdc++.h>
#define dbg(x) if(COND) {cout << #x << "=" << x << "\n";}
#define dbgp(x) if(COND) {cout << #x << "= {" << x.first << "," << x.second << "}\n";}
#define dbgv(x) if(COND) {cout << #x << ": "; for (auto k : x) { cout << k << " "; } cout << "\n";}
#define dbgvp(x) if(COND) {cout << #x << ":\n"; for (auto k : x) { dbgp(k) } cout << "\n";}
#define dbgm(x) if(COND) {int ind = 0; cout << #x << ":\n"; for (auto k : x) { cout << ind++ << ": "; for (auto p : k) {cout << p << " ";} cout << "\n";} cout << "\n";}
#define dbgmp(x) if(COND) {int ind = 0; cout << #x << ":\n"; for (auto k : x) { cout << ind++ << ": "; for (auto p : k) {cout << "{" << p.first << "," << p.second << "} ";} cout << "\n";} cout << "\n";}
#define dbga(x , n) if(COND) {cout << #x << ": "; for(int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << "\n";}
#define dbga2(x , n , m) if(COND) {cout << #x << ":\n"; for(int i = 1; i <= n; i++) { cout << i << ": "; for (int j = 1; j <= m; j++) {cout << a[i][j] << " ";} cout << "\n"; } cout << "\n";}
#define brk(x) if(x) { COND = true; } else { COND = false; }
#define sep if (COND) {cout << "\n-------------------------------\n\n";}
#define dbgdeq(q) if (COND) {cout << #q << ": "; deque<int> qc = q; while(!qc.empty()) {cout << qc.front() << " "; qc.pop_front();} cout << "\n"; }
#define int long long
using namespace std;
bool COND = true;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#define in cin
#define out cout
#endif // LOCAL
int n,m,q;
const int nmax = 300005;
vector<vector<pair<int,int>>> g;
vector<pair<int,int>> lines;
int nrEuler;
///returns the number of inactive edges from node to root
struct Bit {
int v[nmax];
int query(int pos) {
int s = 0;
for (; pos > 1; pos -= (pos &(-pos))) {
s += v[pos];
}
return s;
}
void update(int pos, int val) {
for (; pos <= nrEuler; pos += (pos & (-pos))) {
v[pos] += val;
}
}
};
Bit bit;
vector<int> par,first,last,Rank;
///returns the number of inactive nodes from root to node
int inactive(int node) {
return bit.query(first[node]);
}
void euler(int node, int &ind) {
first[node] = ++ind;
for (auto k : g[node]) {
if (par[node] == k.first) continue;
par[k.first] = node;
Rank[k.first] = Rank[node] + 1;
euler(k.first , ind);
}
last[node] = ++ind;
}
///returns the highest node in the component of 'node', which is the first
///node that has less inactive components than node.
const int MAXPUT = 20;
int lift[MAXPUT][nmax];
void getLift() {
for (int i = 1; i <= n; i++) {
lift[0][i] = par[i];
}
for (int p = 1; (1 << p) <= n; p++) {
for (int i = 1; i <= n; i++) {
lift[p][i] = lift[p - 1][lift[p - 1][i]];
}
}
/*
for (int p = 0; p <= 10; p++) {
for (int i = 1; i <= n; i++) {
cout << "p = " << p << " i = " << i << ": " << lift[p][i] << "\n";
}
cout << "\n";
}cout << "\n";*/
}
int root(int node) {
int nodeInactive = inactive(node);
int r = node;
for (int p = MAXPUT - 1; p >= 0; p--) {
if (lift[p][r] == 0) continue;
if (inactive(lift[p][r]) == nodeInactive) {
r = lift[p][r];
}
}
return r;
}
int32_t main() {
in >> n >> m >> q;
lines.resize(n);
g.resize(n + 1);
par.resize(n + 1);
first.resize(n + 1);
last.resize(n + 1);
Rank.resize(n + 1);
for (int i = 1; i < n; i++) {
int u,v;
in >> u >> v;
g[u].push_back({v,i});
g[v].push_back({u,i});
lines[i] = {u,v};
}
nrEuler = 0;
euler(1 , nrEuler);
auto deactivate = [&](int u, int v) {
///u is parent, v is child
if (Rank[u] > Rank[v]) swap(u,v);
bit.update(first[v] , 1);
bit.update(last[v] , -1);
};
auto activate = [&](int u, int v) {
if (Rank[u] > Rank[v]) swap(u,v);
bit.update(first[v] , -1);
bit.update(last[v] , 1);
};
for (int i = 1; i < n; i++) {
deactivate(lines[i].first , lines[i].second);
}
getLift();
vector<int> sol(n + 1 , 1);
vector<int> status(n , 0); /// 0 = inactive, 1 = active
vector<int> qs(m + 1);
vector<int> appearence(n + 1, 0);
for (int i = 1; i <= m; i++) {
in >> qs[i];
appearence[qs[i]]++;
}
vector<int> qs2;
vector<int> needed(n , 0);
qs2.push_back(0);
for (int i = 1; i < n; i++) {
if (appearence[i] > 0 && appearence[i] % 2 == 0) needed[i] = 2;
else if (appearence[i] > 0)
needed[i] = 1;
}
// dbgv(appearence);
// dbgv(needed);
for (int i = 1; i <= m; i++) {
if (appearence[qs[i]] > needed[qs[i]]) {
appearence[qs[i]]--;
} else {
qs2.push_back(qs[i]);
}
}
//dbgv(qs2);
for (int i = 1; i < qs2.size(); i++) {
int ind = qs2[i];
int u = lines[ind].first;
int v = lines[ind].second;
///u is parent, v is child
if (Rank[u] > Rank[v]) swap(u,v);
if (status[ind] == 0) { /// its currently inactive
int r = root(u);
sol[r] += sol[v];
// lastAdded[ind] = sol[v];
activate(u , v);
status[ind] = 1;
} else {
sol[v] = sol[root(u)];
deactivate(u,v);
status[ind] = 0;
}
}
for (int i = 1; i <= q; i++) {
int x;
in >> x;
out << sol[root(x)] << "\n";
}
}
Compilation message
synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:174:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (int i = 1; i < qs2.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
36016 KB |
Output is correct |
| 2 |
Correct |
139 ms |
35488 KB |
Output is correct |
| 3 |
Correct |
164 ms |
38316 KB |
Output is correct |
| 4 |
Correct |
156 ms |
38304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
684 ms |
39248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
