oj.uz

Submission #68317

# Submission time Handle Problem Language Result Execution time Memory
68317 2018-08-16T16:48:31 Z top34051 Synchronization (JOI13_synchronization) C++17
100 / 100
 1802 ms 96772 KB 
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;

int n,m,q;
vector<pii> way[maxn];
pii e[maxn];

int h[maxn], cur, st[maxn], ft[maxn];
set<pii> seg[maxn*4];
int  open[maxn];

int res[maxn], wow[maxn];

void dfs(int u, int last) {
	h[u] = h[last] + 1;
	st[u] = ++cur;
	for(auto tmp : way[u]) {
		int v = tmp.X, id = tmp.Y;
		if(v==last) continue;
		e[id] = {u,v};
		dfs(v,u);
	}
	ft[u] = cur;
}

void update_add(int pos, int l, int r, int x, int y, int u) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		seg[pos].insert({-h[u],u});
		return ;
	}
	int mid = (l+r)/2;
	update_add(pos<<1,l,mid,x,y,u);
	update_add(pos<<1|1,mid+1,r,x,y,u);
}

void update_del(int pos, int l, int r, int x, int y, int u) {
	if(l>r || r<x || y<l) return ;
	if(x<=l && r<=y) {
		seg[pos].erase({-h[u],u});
		return ;
	}
	int mid = (l+r)/2;
	update_del(pos<<1,l,mid,x,y,u);
	update_del(pos<<1|1,mid+1,r,x,y,u);
}

pii query(int pos, int l, int r, int x) {
	if(l>r || r<x || x<l) return {0,0};
	pii tmp = {0,0};
	if(seg[pos].size()!=0) tmp = *seg[pos].begin();
	if(l==r) return tmp;
	int mid = (l+r)/2;
	return min(tmp, min(query(pos<<1,l,mid,x), query(pos<<1|1,mid+1,r,x)));
}

int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++) {
		int u,v; scanf("%d%d",&u,&v);
		way[u].push_back({v,i});
		way[v].push_back({u,i});
	}

	dfs(1,0);
	for(int u=1;u<=n;u++) {
        update_add(1,1,n,st[u],ft[u],u);
        res[u] = 1;
    }

	for(int i=1;i<=m;i++) {
		int x; scanf("%d",&x);
		int u = e[x].X, v = e[x].Y;
		if(!open[x]) {
			int root = query(1,1,n,st[u]).Y;
//			printf("root = %d  %d + %d - %d\n",root,res[root],res[v],wow[v]);
			res[root] = res[root] + res[v] - wow[v];
			res[v] = 0;
			wow[v] = 0;
			update_del(1,1,n,st[v],ft[v],v);
			open[x] = 1;
		}
		else {
			int root = query(1,1,n,st[u]).Y;
			res[v] = res[root];
			wow[v] = res[root];
//            printf("root = %d  %d  %d  %d\n",root,res[root],res[v],wow[v]);
			update_add(1,1,n,st[v],ft[v],v);
			open[x] = 0;
        }
	}

	while(q--) {
		int u; scanf("%d",&u);
		int root = query(1,1,n,st[u]).Y;
		printf("%d\n",res[root]);
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u,v; scanf("%d%d",&u,&v);
            ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:77:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d",&x);
          ~~~~~^~~~~~~~~
synchronization.cpp:99:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u; scanf("%d",&u);
          ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21572 KB Output is correct
2 Correct 21 ms 21572 KB Output is correct
3 Correct 18 ms 21572 KB Output is correct
4 Correct 19 ms 21624 KB Output is correct
5 Correct 19 ms 21676 KB Output is correct
6 Correct 23 ms 21808 KB Output is correct
7 Correct 56 ms 23360 KB Output is correct
8 Correct 56 ms 23552 KB Output is correct
9 Correct 56 ms 24000 KB Output is correct
10 Correct 727 ms 40012 KB Output is correct
11 Correct 681 ms 40336 KB Output is correct
12 Correct 1671 ms 75908 KB Output is correct
13 Correct 377 ms 75908 KB Output is correct
14 Correct 432 ms 75908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 75908 KB Output is correct
2 Correct 334 ms 75908 KB Output is correct
3 Correct 408 ms 78028 KB Output is correct
4 Correct 408 ms 78028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 78028 KB Output is correct
2 Correct 20 ms 78028 KB Output is correct
3 Correct 20 ms 78028 KB Output is correct
4 Correct 19 ms 78028 KB Output is correct
5 Correct 20 ms 78028 KB Output is correct
6 Correct 24 ms 78028 KB Output is correct
7 Correct 97 ms 78028 KB Output is correct
8 Correct 1802 ms 78264 KB Output is correct
9 Correct 1772 ms 78264 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1764 ms 81080 KB Output is correct
2 Correct 427 ms 81584 KB Output is correct
3 Correct 423 ms 84268 KB Output is correct
4 Correct 454 ms 86744 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 86744 KB Output is correct
2 Correct 20 ms 86744 KB Output is correct
3 Correct 22 ms 86744 KB Output is correct
4 Correct 24 ms 86744 KB Output is correct
5 Correct 29 ms 86744 KB Output is correct
6 Correct 64 ms 86744 KB Output is correct
7 Correct 866 ms 86744 KB Output is correct
8 Correct 1735 ms 86744 KB Output is correct
9 Correct 494 ms 86744 KB Output is correct
10 Correct 503 ms 86744 KB Output is correct
11 Correct 479 ms 86744 KB Output is correct
12 Correct 460 ms 86744 KB Output is correct
13 Correct 432 ms 96772 KB Output is correct