oj.uz

Submission #209262

# Submission time Handle Problem Language Result Execution time Memory
209262 2020-03-13T14:13:48 Z dennisstar Synchronization (JOI13_synchronization) C++17
100 / 100
 390 ms 29432 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 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) {
	spt[n].eb(p); in[n]=++c;
	for (int i=0; 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+1;
}

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

int main() {
	cin.tie(0)->sync_with_stdio(0);
	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 (spt[X[i]][0]==Y[i]) swap(X[i], Y[i]);
	for (int i=1; i<=N; i++) Z[i]=1, upd(in[i], 1), upd(out[i], -1);
	while (M--) {
		int d, p; cin>>d; p=gp(X[d]);
		if (chk[d]==0) {
			upd(in[Y[d]], -1); upd(out[Y[d]], 1);
			Z[p]+=Z[Y[d]]-lst[d];
		}
		if (chk[d]==1) {
			upd(in[Y[d]], 1); upd(out[Y[d]], -1);
			Z[Y[d]]=lst[d]=Z[p];
		}
		chk[d]=1-chk[d];
	}
	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:18:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<spt[spt[n][i]].size(); i++) spt[n].eb(spt[spt[n][i]][i]);
                ~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'int gp(int)':
synchronization.cpp:25:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=20; i>=0; i--) if (i<spt[t].size()&&x==get(in[spt[t][i]])) t=spt[t][i];
                                ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 9 ms 5368 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 22 ms 6136 KB Output is correct
8 Correct 21 ms 6008 KB Output is correct
9 Correct 21 ms 6136 KB Output is correct
10 Correct 260 ms 15736 KB Output is correct
11 Correct 278 ms 15864 KB Output is correct
12 Correct 359 ms 29048 KB Output is correct
13 Correct 120 ms 14832 KB Output is correct
14 Correct 184 ms 15612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 21756 KB Output is correct
2 Correct 151 ms 21748 KB Output is correct
3 Correct 198 ms 28940 KB Output is correct
4 Correct 197 ms 28792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 9 ms 5244 KB Output is correct
7 Correct 29 ms 7288 KB Output is correct
8 Correct 385 ms 29304 KB Output is correct
9 Correct 385 ms 29304 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 29304 KB Output is correct
2 Correct 221 ms 29176 KB Output is correct
3 Correct 231 ms 29432 KB Output is correct
4 Correct 219 ms 29380 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 9 ms 5112 KB Output is correct
6 Correct 24 ms 6136 KB Output is correct
7 Correct 305 ms 16248 KB Output is correct
8 Correct 390 ms 29304 KB Output is correct
9 Correct 132 ms 15472 KB Output is correct
10 Correct 204 ms 16120 KB Output is correct
11 Correct 164 ms 22392 KB Output is correct
12 Correct 168 ms 22544 KB Output is correct
13 Correct 211 ms 29432 KB Output is correct