답안 #49891 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49891	2018-06-04T11:08:40 Z	tmwilliamlin168	동기화 (JOI13_synchronization)	C++14	100 / 100	7499 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];
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)+1]; //2 nodes per layer * logn=18 layers * total updates

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;
		if(lsti) {
			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, int fav) {
	psh(sti[u]);
	upd(sti[u], fav, m, 1);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		dfs4(v, u, av[e][1].fi);
		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, 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) {
		int dj;
		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--) {
		int ck;
		cin >> ck, --ck;
		cout << ans[ck] << "\n";
	}
}

Compilation message

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:42: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:112: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, int)':
synchronization.cpp:135: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	5112 KB	Output is correct
2	Correct	5 ms	5112 KB	Output is correct
3	Correct	5 ms	5148 KB	Output is correct
4	Correct	5 ms	5164 KB	Output is correct
5	Correct	6 ms	5164 KB	Output is correct
6	Correct	17 ms	6316 KB	Output is correct
7	Correct	293 ms	21932 KB	Output is correct
8	Correct	262 ms	21960 KB	Output is correct
9	Correct	303 ms	21960 KB	Output is correct
10	Correct	5265 ms	208584 KB	Output is correct
11	Correct	4594 ms	208584 KB	Output is correct
12	Correct	6563 ms	215200 KB	Output is correct
13	Correct	1014 ms	215200 KB	Output is correct
14	Correct	3429 ms	215200 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2548 ms	215200 KB	Output is correct
2	Correct	2521 ms	215200 KB	Output is correct
3	Correct	3397 ms	215200 KB	Output is correct
4	Correct	3885 ms	215200 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	215200 KB	Output is correct
2	Correct	6 ms	215200 KB	Output is correct
3	Correct	7 ms	215200 KB	Output is correct
4	Correct	9 ms	215200 KB	Output is correct
5	Correct	6 ms	215200 KB	Output is correct
6	Correct	27 ms	215200 KB	Output is correct
7	Correct	353 ms	215200 KB	Output is correct
8	Correct	6944 ms	215420 KB	Output is correct
9	Correct	6294 ms	215420 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6596 ms	215468 KB	Output is correct
2	Correct	3914 ms	215468 KB	Output is correct
3	Correct	3685 ms	215468 KB	Output is correct
4	Correct	3429 ms	215468 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 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	7 ms	215468 KB	Output is correct
5	Correct	26 ms	215468 KB	Output is correct
6	Correct	295 ms	215468 KB	Output is correct
7	Correct	5555 ms	215468 KB	Output is correct
8	Correct	7499 ms	215468 KB	Output is correct
9	Correct	1285 ms	215468 KB	Output is correct
10	Correct	3635 ms	215468 KB	Output is correct
11	Correct	2499 ms	215468 KB	Output is correct
12	Correct	2232 ms	215468 KB	Output is correct
13	Correct	3537 ms	215468 KB	Output is correct

답안 #49891

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