Submission #209254

#	Time	Username	Problem	Language	Result	Execution time	Memory
209254		dennisstar	Synchronization (JOI13_synchronization)	C++17	0 / 100	815 ms	32608 KiB

synchronization

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef vector<int> vim;

const int MX = 100005;

int N, M, Q, c, X[MX], Y[MX], Z[MX], lst[MX];
int dep[MX], in[MX], out[MX], chk[MX];
vim adj[MX], spt[MX];

int F[MX];
void upd(int t, int v) { while (t<=N) F[t]+=v, t+=t&-t; }
int get(int t) { int r=0; while (t) r+=F[t], t-=t&-t; return r; }

void dfs(int n, int p) {
	if (p) spt[n].eb(p);
	dep[n]=dep[p]+1; in[n]=++c;
	for (int i=0; p&&i<spt[spt[n][i]].size(); i++) spt[n].eb(spt[spt[n][i]][i]);
	for (auto &i:adj[n]) if (i!=p) dfs(i, n);
	out[n]=c;
}

int gp(int t) {
	int x=get(in[t]);
	for (int i=20; i>=0; i--) if (i<spt[t].size()&&x-(1<<i)==get(spt[t][i])) t=spt[t][i], x-=(1<<i);
	return t;
}

int main() {
	cin>>N>>M>>Q;
	for (int i=1; i<N; i++) cin>>X[i]>>Y[i], adj[X[i]].eb(Y[i]), adj[Y[i]].eb(X[i]);
	dfs(1, 0);
	for (int i=1; i<N; i++) if (dep[X[i]]>dep[Y[i]]) swap(X[i], Y[i]);
	for (int i=1; i<=N; i++) Z[i]=1;
	while (M--) {
		int d; cin>>d;
		if (chk[d]==0) {
			chk[d]=1;
			upd(in[Y[d]], 1); upd(out[Y[d]]+1, -1);
			int p=gp(X[d]); Z[p]+=Z[Y[d]]-lst[d];
		}
		if (chk[d]==1) {
			chk[d]=0;
			upd(in[Y[d]], -1); upd(out[Y[d]]+1, 1);
			int p=gp(X[d]); Z[Y[d]]=lst[d]=Z[p];
		}
	}
	for (int i=1; i<=N; i++) Z[i]=Z[gp(i)];
	while (Q--) cin>>c, cout<<Z[c]<<'\n';
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; p&&i<spt[spt[n][i]].size(); i++) spt[n].eb(spt[spt[n][i]][i]);
                   ~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'int gp(int)':
synchronization.cpp:26:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=20; i>=0; i--) if (i<spt[t].size()&&x-(1<<i)==get(spt[t][i])) t=spt[t][i], x-=(1<<i);
                                ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40