답안 #52432 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52432	2018-06-26T01:21:52 Z	tmwilliamlin168	동기화 (JOI13_synchronization)	C++14	100 / 100	7501 ms	215468 KB

synchronization

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #52432

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 10.0 / 10.0

Subtask #4 20.0 / 20.0

Subtask #5 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
10.0 / 10.0

Subtask #4
20.0 / 20.0

Subtask #5
40.0 / 40.0