oj.uz

Submission #32172

# Submission time Handle Problem Language Result Execution time Memory
32172 2017-10-01T17:50:04 Z gs14004 Synchronization (JOI13_synchronization) C++14
100 / 100
 256 ms 25324 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 200005;
typedef long long lint;

struct lct{
	struct node{
		node *p, *l, *r, *pp;
		int idx;
		node(int _idx){
			p = l = r = pp = NULL;
			idx = _idx;
		}
	}*n[MAXN];
	void init(int v){
		for(int i=1; i<=v; i++) n[i] = new node(i);
	}
	void rotate(node *x){
		if(!x->p) return;
		node *p = x->p;
		bool is_left = (p->l == x);
		node *b = (is_left ? x->r : x->l);
		x->p = p->p;
		if(x->p && x->p->l == p) x->p->l = x;
		if(x->p && x->p->r == p) x->p->r = x;
		if(is_left){
			if(b) b->p = p;
			p->l = b;
			p->p = x;
			x->r = p;
		}
		else{
			if(b) b->p = p;
			p->r = b;
			p->p = x;
			x->l = p;
		}
		if(p->pp){
			x->pp = p->pp;
			p->pp = NULL;
		}
	}
	void splay(node *x){
		while(x->p){
			node *p = x->p;
			node *g = p->p;
			if(g){
				if((p->l == g) ^ (g->l == p)) rotate(p);
				else rotate(x);
			}
			rotate(x);
		}
	}
	void access(node *x){
		splay(x);
		if(x->r){
			x->r->p = NULL;
			x->r->pp = x;
			x->r = NULL;
		}
		while(x->pp){
			node *nxt = x->pp;
			splay(nxt);
			if(nxt->r){
				nxt->r->p = NULL;
				nxt->r->pp = nxt;
			}
			nxt->r = x;
			x->p = nxt;
			x->pp = NULL;
			splay(x);
		}
	}
	void link(int par, int son){
		node *v = n[par];
		node *w = n[son];
		access(v);
		access(w);
		assert(w->l == NULL);
		v->r = w;
		w->p = v;
	}
	void cut(int v){
		node *x = n[v];
		access(x);
		if(x->l){
			x->l->p = NULL;
			x->l = NULL;
		}
	}
	int root(int v){
		access(n[v]);
		node *p = n[v];
		while(p->l) p = p->l;
		access(p);
		return p->idx;
	}
}lct;


vector<int> gph[MAXN];
int par[MAXN], s[MAXN], e[MAXN];

void dfs(int x, int p){
	par[x] = p;
	for(auto &i : gph[x]){
		if(i == p) continue;
		dfs(i, x);
	}
}

int chk[MAXN], las[MAXN], cnt[MAXN];

int main(){
	int n, m, q;
	scanf("%d %d %d",&n,&m,&q);
	lct.init(n);
	for(int i=1; i<n; i++){
		scanf("%d %d",&s[i],&e[i]);
		gph[s[i]].push_back(e[i]);
		gph[e[i]].push_back(s[i]);
	}
	dfs(1, -1);
	for(int i=1; i<n; i++) if(par[s[i]] == e[i]) swap(s[i], e[i]);
	fill(cnt + 1, cnt + n + 1, 1);
	for(int i=0; i<m; i++){
		int v;
		scanf("%d",&v);
		if(!chk[v]){
			int k = cnt[lct.root(s[v])] + cnt[lct.root(e[v])] - las[v];
			lct.link(s[v], e[v]);
			cnt[lct.root(s[v])] = k;
		}
		else{
			las[v] = cnt[lct.root(s[v])];
			lct.cut(e[v]);
			cnt[lct.root(e[v])] = las[v];
		}
		chk[v] ^= 1;
	}
	while(q--){
		int t;
		scanf("%d",&t);
		printf("%d\n", cnt[lct.root(t)]);
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:117:28: 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:120:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s[i],&e[i]);
                             ^
synchronization.cpp:129:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v);
                 ^
synchronization.cpp:144:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12968 KB Output is correct
2 Correct 0 ms 12968 KB Output is correct
3 Correct 0 ms 12968 KB Output is correct
4 Correct 3 ms 12968 KB Output is correct
5 Correct 0 ms 12968 KB Output is correct
6 Correct 0 ms 13100 KB Output is correct
7 Correct 13 ms 13760 KB Output is correct
8 Correct 16 ms 13760 KB Output is correct
9 Correct 13 ms 13760 KB Output is correct
10 Correct 256 ms 20888 KB Output is correct
11 Correct 229 ms 20888 KB Output is correct
12 Correct 199 ms 25320 KB Output is correct
13 Correct 159 ms 21272 KB Output is correct
14 Correct 193 ms 20888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 23304 KB Output is correct
2 Correct 73 ms 23208 KB Output is correct
3 Correct 83 ms 25316 KB Output is correct
4 Correct 66 ms 25316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12968 KB Output is correct
2 Correct 0 ms 12968 KB Output is correct
3 Correct 3 ms 12968 KB Output is correct
4 Correct 0 ms 12968 KB Output is correct
5 Correct 0 ms 12968 KB Output is correct
6 Correct 3 ms 13100 KB Output is correct
7 Correct 13 ms 14108 KB Output is correct
8 Correct 193 ms 25316 KB Output is correct
9 Correct 169 ms 25316 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 25316 KB Output is correct
2 Correct 109 ms 25288 KB Output is correct
3 Correct 89 ms 25324 KB Output is correct
4 Correct 116 ms 25316 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12968 KB Output is correct
2 Correct 0 ms 12968 KB Output is correct
3 Correct 0 ms 12968 KB Output is correct
4 Correct 0 ms 12968 KB Output is correct
5 Correct 0 ms 13100 KB Output is correct
6 Correct 9 ms 13760 KB Output is correct
7 Correct 226 ms 20888 KB Output is correct
8 Correct 173 ms 25316 KB Output is correct
9 Correct 133 ms 21272 KB Output is correct
10 Correct 206 ms 20888 KB Output is correct
11 Correct 109 ms 23308 KB Output is correct
12 Correct 123 ms 23308 KB Output is correct
13 Correct 76 ms 25320 KB Output is correct