#include <bits/stdc++.h>
//#ifndef ONLINE_JUDGE
//#include <C:\debug.hpp>
//#endif // ONLINE_JUDGE
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Synchronization"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, m, q;
int cl[maxn], ans[maxn], last[maxn];
int p[maxn], In[maxn], Out[maxn];
pair<int, int> E[maxn];
vector<int> edges[maxn];
void pre_dfs(int u, int par) {
static int Time = 0;
In[u] = ++Time, p[Time] = u;
for(int v : edges[u]) if(v != par) {
pre_dfs(v, u);
}
Out[u] = Time;
}
struct IT {
int st[4 * maxn];
void update(int x, int val, int id = 1, int l = 1, int r = n) {
if(l > x || r < x) return;
if(l == r) return st[id] = val, void();
int mid = (l + r) >> 1;
update(x, val, _left), update(x, val, _right);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int x, int val, int id = 1, int l = 1, int r = n) {
if(l > x || st[id] < val) return -1;
if(l == r) return p[l];
int mid = (l + r) >> 1;
int w = get(x, val, _right);
if(w == -1) w = get(x, val, _left);
return w;
}
} St;
void solve()
{
cin >> n >> m >> q;
fi(i, 1, n - 1) {
int x, y; cin >> x >> y;
E[i] = {x, y};
edges[x].push_back(y), edges[y].push_back(x);
}
pre_dfs(1, 0);
fi(i, 1, n) {
St.update(In[i], Out[i]);
ans[i] = 1;
}
fi(i, 1, m) {
int id, u, v; cin >> id;
tie(u, v) = E[id]; if(In[u] > In[v]) swap(u, v);
int p = St.get(In[u], Out[u]);
if(!cl[id]) {
ans[p] += ans[v] - last[v];
St.update(In[v], 0);
}
else {
last[v] = ans[v], ans[v] = ans[p];
St.update(In[v], Out[v]);
}
cl[id] ^= 1;
}
fi(i, 1, q) {
int x; cin >> x;
cout << ans[St.get(In[x], Out[x])] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen(Neco".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen(Neco".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
117 ms |
20200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
