oj.uz

Submission #52432

# Submission time Handle Problem Language Result Execution time Memory
52432 2018-06-26T01:21:52 Z tmwilliamlin168 Synchronization (JOI13_synchronization) C++14
100 / 100
 7501 ms 215468 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define fi first
#define se second
 
const int mxN=1e5, mxM=2e5;
int n, m, q, x[mxN-1], y[mxN-1], lb[mxN-1], ans[mxN], centP[mxN], sz[mxN], rt1, sts=2, bsts, sti[mxN], mlt[mxN], dj, ck;
vector<pii> av[mxN-1];
vector<int> adj[mxN], cn;
 
struct node {
	bool lz1;
	int lz2, v, lc, rc;
} st[2*18*(2*mxN+mxM/2)+2*mxM]; //2 nodes per layer * logn=18 layers * total updates + max nodes in a segtree
 
inline void psh(int &sti, int v=0, bool x1=0, int x2=0) {
	if(!sti||st[sti].v!=v) {
		st[sts]=st[sti];
		st[sts].v=v;
		sti=sts++;
	}
	if(x1)
		st[sti].lz1=1, st[sti].lz2=0;
	st[sti].lz2+=x2;
}
 
void upd(int sti, int l1, int r1, int x, int v=0, int l2=0, int r2=m) {
	if(l1>r1)
		return;
	if(l1<=l2&&r2<=r1) {
		st[sti].lz1=1, st[sti].lz2=x;
		return;
	}
	psh(st[sti].lc, v, st[sti].lz1, st[sti].lz2);
	psh(st[sti].rc, v, st[sti].lz1, st[sti].lz2);
	st[sti].lz1=st[sti].lz2=0;
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(st[sti].lc, l1, r1, x, v, l2, m2);
	if(m2<r1)
		upd(st[sti].rc, l1, r1, x, v, m2+1, r2);
}
 
int qry(int sti, int l1, int l2=0, int r2=m) {
	if(!sti)
		return 0;
	if(st[sti].lz1)
		return st[sti].lz2;
	int m2=(l2+r2)/2;
	return st[sti].lz2+(l1<=m2?qry(st[sti].lc, l1, l2, m2):qry(st[sti].rc, l1, m2+1, r2));
}
 
void mrg(int &sti1, int sti2) {
	if(!sti1||!sti2) {
		sti1^=sti2;
		return;
	}
	st[sti1].lz2+=st[sti2].lz2;
	if(st[sti2].lz1)
		return;
	if(st[sti1].lz1) {
		st[sti1].lz1=0;
		st[sti1].lc=st[sti2].lc, st[sti1].rc=st[sti2].rc;
		return;
	}
	mrg(st[sti1].lc, st[sti2].lc);
	mrg(st[sti1].rc, st[sti2].rc);
}
 
inline void clst() {
	while(sts>bsts)
		st[--sts]={};
	for(int cni : cn)
		sti[cni]=0;
}
 
void dfs1(int u, int p) {
	sz[u]=1;
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		dfs1(v, u);
		sz[u]+=sz[v];
	}
}
 
int dfs2(int u, int p, int szr) {
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v!=p&&centP[v]==-1&&sz[v]>szr/2)
			return dfs2(v, u, szr);
	}
	return u;
}
 
void dfs3(int u, int p) {
	cn.push_back(u);
	mlt[u]=qry(sti[u], m);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		sti[v]=sti[u];
		psh(sti[v], v);
		for(int i=0; i<av[e].size()-1; ++i)
			upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se), v);
		dfs3(v, u);
	}
}
 
void dfs5(int u, int p) {
	ans[u]-=qry(sti[rt1], mlt[u]);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v!=p&&centP[v]==-1)
			dfs5(v, u);
	}
}
 
void dfs4(int u, int p) {
	psh(sti[u]);
	upd(sti[u], 1, m, 1);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		dfs4(v, u);
		for(int i=0; i<av[e].size()-1; ++i)
			upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se));
		if(p==-1) {
			rt1=v;
			dfs5(v, u);
		}
		mrg(sti[u], sti[v]);
	}
}
 
void cd(int u, int p) {
	int c=dfs2(u, -1, sz[u]);
	centP[c]=p;
	dfs1(c, -1);
	sti[c]=1;
	psh(sti[c], c);
	dfs3(c, -1);
	clst();
	dfs4(c, -1);
	for(int cni : cn)
		ans[cni]+=qry(sti[c], mlt[cni]);
	ans[c]+=!mlt[c];
	clst();
	cn.clear();
	for(int e : adj[c]) {
		int v=c^x[e]^y[e];
		if(centP[v]==-1)
			cd(v, c);
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for(int i=0; i<n-1; ++i) {
		cin >> x[i] >> y[i], --x[i], --y[i];
		adj[x[i]].push_back(i);
		adj[y[i]].push_back(i);
		av[i].push_back({0, 0});
	}
	for(int i=1; i<=m; ++i) {
		cin >> dj, --dj;
		if(lb[dj]) {
			av[dj].push_back({lb[dj], i-1});
			lb[dj]=0;
		} else
			lb[dj]=i;
	}
	for(int i=0; i<n-1; ++i)
		av[i].push_back({lb[i]?lb[i]:m+1, m+1});
	for(int i=0; i<=m; ++i)
		upd(1, i, i, i, -1);
	bsts=sts;
	memset(centP, -1, 4*n);
	dfs1(0, -1);
	cd(0, -2);
	while(q--) {
		cin >> ck, --ck;
		cout << ans[ck] << "\n";
	}
}

Compilation message

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:38:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  st[sti].lz1=st[sti].lz2=0;
              ~~~~~~~~~~~^~
synchronization.cpp: In function 'void dfs3(int, int)':
synchronization.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void dfs4(int, int)':
synchronization.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5148 KB Output is correct
3 Correct 6 ms 5264 KB Output is correct
4 Correct 7 ms 5264 KB Output is correct
5 Correct 9 ms 5268 KB Output is correct
6 Correct 23 ms 6444 KB Output is correct
7 Correct 263 ms 21824 KB Output is correct
8 Correct 286 ms 21920 KB Output is correct
9 Correct 281 ms 21956 KB Output is correct
10 Correct 5320 ms 208692 KB Output is correct
11 Correct 5117 ms 208756 KB Output is correct
12 Correct 7150 ms 215284 KB Output is correct
13 Correct 1002 ms 215284 KB Output is correct
14 Correct 3870 ms 215284 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2556 ms 215284 KB Output is correct
2 Correct 2412 ms 215284 KB Output is correct
3 Correct 3669 ms 215284 KB Output is correct
4 Correct 3513 ms 215284 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 215284 KB Output is correct
2 Correct 6 ms 215284 KB Output is correct
3 Correct 6 ms 215284 KB Output is correct
4 Correct 7 ms 215284 KB Output is correct
5 Correct 6 ms 215284 KB Output is correct
6 Correct 25 ms 215284 KB Output is correct
7 Correct 394 ms 215284 KB Output is correct
8 Correct 7376 ms 215452 KB Output is correct
9 Correct 7501 ms 215468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6940 ms 215468 KB Output is correct
2 Correct 3945 ms 215468 KB Output is correct
3 Correct 4019 ms 215468 KB Output is correct
4 Correct 3613 ms 215468 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 215468 KB Output is correct
2 Correct 6 ms 215468 KB Output is correct
3 Correct 6 ms 215468 KB Output is correct
4 Correct 6 ms 215468 KB Output is correct
5 Correct 19 ms 215468 KB Output is correct
6 Correct 262 ms 215468 KB Output is correct
7 Correct 5362 ms 215468 KB Output is correct
8 Correct 7341 ms 215468 KB Output is correct
9 Correct 1156 ms 215468 KB Output is correct
10 Correct 3783 ms 215468 KB Output is correct
11 Correct 2439 ms 215468 KB Output is correct
12 Correct 2628 ms 215468 KB Output is correct
13 Correct 3864 ms 215468 KB Output is correct