oj.uz

Submission #209254

# Submission time Handle Problem Language Result Execution time Memory
209254 2020-03-13T13:55:51 Z dennisstar Synchronization (JOI13_synchronization) C++17
0 / 100
 815 ms 32608 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Incorrect 8 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 330 ms 24556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 815 ms 32608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Incorrect 8 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -