답안 #52429 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52429	2018-06-26T01:09:34 Z	tmwilliamlin168	동기화 (JOI13_synchronization)	C++14	100 / 100	7911 ms	256116 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) {
	int lsti=sti;
	if(!sti||st[sti].v!=v) {
		sti=sts++;
		st[sti].v=v;
		st[sti].lc=st[lsti].lc, st[sti].rc=st[lsti].rc;
		st[sti].lz1=st[lsti].lz1, st[sti].lz2=st[lsti].lz2;
	}
	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:40: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:110: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:133: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	7 ms	5112 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	6 ms	5172 KB	Output is correct
4	Correct	6 ms	5176 KB	Output is correct
5	Correct	6 ms	5400 KB	Output is correct
6	Correct	20 ms	6536 KB	Output is correct
7	Correct	326 ms	22320 KB	Output is correct
8	Correct	278 ms	22536 KB	Output is correct
9	Correct	287 ms	22744 KB	Output is correct
10	Correct	4956 ms	211644 KB	Output is correct
11	Correct	5224 ms	213900 KB	Output is correct
12	Correct	7593 ms	222948 KB	Output is correct
13	Correct	1131 ms	222948 KB	Output is correct
14	Correct	3775 ms	222948 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2617 ms	222948 KB	Output is correct
2	Correct	2571 ms	222948 KB	Output is correct
3	Correct	3864 ms	222948 KB	Output is correct
4	Correct	4250 ms	222948 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	222948 KB	Output is correct
2	Correct	8 ms	222948 KB	Output is correct
3	Correct	8 ms	222948 KB	Output is correct
4	Correct	7 ms	222948 KB	Output is correct
5	Correct	7 ms	222948 KB	Output is correct
6	Correct	26 ms	222948 KB	Output is correct
7	Correct	476 ms	222948 KB	Output is correct
8	Correct	7911 ms	237500 KB	Output is correct
9	Correct	7568 ms	240252 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7801 ms	243128 KB	Output is correct
2	Correct	3959 ms	243128 KB	Output is correct
3	Correct	3903 ms	243128 KB	Output is correct
4	Correct	3711 ms	243128 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	243128 KB	Output is correct
2	Correct	7 ms	243128 KB	Output is correct
3	Correct	7 ms	243128 KB	Output is correct
4	Correct	7 ms	243128 KB	Output is correct
5	Correct	20 ms	243128 KB	Output is correct
6	Correct	357 ms	243128 KB	Output is correct
7	Correct	5522 ms	246644 KB	Output is correct
8	Correct	7712 ms	256116 KB	Output is correct
9	Correct	1055 ms	256116 KB	Output is correct
10	Correct	3511 ms	256116 KB	Output is correct
11	Correct	2451 ms	256116 KB	Output is correct
12	Correct	2529 ms	256116 KB	Output is correct
13	Correct	3822 ms	256116 KB	Output is correct

답안 #52429

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