oj.uz

Submission #25496

# Submission time Handle Problem Language Result Execution time Memory
25496 2017-06-22T12:48:30 Z zigui Synchronization (JOI13_synchronization) C++14
100 / 100
 306 ms 24540 KB 
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<algorithm>
#include<stdio.h>

using namespace std;

const int MX = 2e5;

struct node{
	node *link[2], *par, *path_parent;
};

struct linkcuttree{
	node N[MX];

	void clear(int s){
		for(int i=0;i<s;i++) N[i].link[0] = N[i].link[1] = N[i].par = N[i].path_parent = 0;
	}

	inline int dir(node *x){ return x->par->link[0] != x; }

	void rotate(node *n) // To 
	{
		if( !n->par ) return;
		node *p = n->par;
		int d = dir(n);
		n->path_parent = p->path_parent; p->path_parent = NULL;
		p->link[d] = n->link[!d];   if( n->link[!d] ) n->link[!d]->par = p;
		n->par = p->par;  if( p->par ) p->par->link[ dir(p) ] = n;
		n->link[!d] = p;  p->par = n;
	}

	void splay(node *x){
		while( x->par ){
			if( !x->par->par );
			else if(dir(x) == dir(x->par)) rotate(x->par);
			else rotate(x);
			rotate(x);
		}
	}

	void access(node* x)
	{
		splay(x);
		if( x->link[1] ) x->link[1]->path_parent = x, x->link[1]->par = NULL;
		x->link[1] = NULL;
		while( x->path_parent ){
			node *pp = x->path_parent, *r;
			splay(pp);
			r = pp->link[1];
			if( r ) r->par = NULL, r->path_parent = pp;
			pp->link[1] = x; x->par = pp;
			x->path_parent = NULL;
			splay(x);
		}
	}

	void cut(int u)
	{
		access(N+u);
		if( N[u].link[0] ) N[u].link[0]->par = NULL;
		N[u].link[0] = NULL;
	}

	void link(int u, int v) // u를 v에, u가 루트여야 함
	{
		access(N+u);
		access(N+v);
		if(N[u].link[0]) printf("ERROR");
		N[u].link[0] = N+v; N[v].par = N+u;
	}

	int root(int u)
	{
		access( N+u );
		node* ans = N+u;
		while( ans->link[0] ) ans = ans->link[0];
		splay(ans);
		return ans - N;
	}
}LCT;

typedef pair<int,int> pii;

vector<int> G[MX];
pii E[MX];
int a, b, c;
int N, M, Q;
int state[MX], lev[MX], lst[MX], value[MX];

void dfs(int x, int p){
	lev[x] = lev[p] + 1;
	for(int c : G[x]){
		if( c != p ) dfs(c, x);
	}
}

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i = 1; i <= N; i++) value[i] = 1;
	for(int i = 1; i < N; i++){
		scanf("%d%d", &a, &b);
		E[i] = pii(a, b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1, 0);
	for(int i = 1; i <= M; i++){
		scanf("%d", &c);
		int a = E[c].first, b = E[c].second;
		if( lev[a] > lev[b] ) swap(a, b);
	
		state[c] ^= 1;
		if( state[c] == 1 ){
			int p = value[LCT.root(a)];
			int q = value[LCT.root(b)];
			LCT.link(b, a);
			value[LCT.root(a)] = p+q - lst[c];
		}
		else{
			int t = value[LCT.root(b)]; lst[c] = t;
			LCT.cut(b); value[LCT.root(b)] = t;
		}
	}
	for(int i = 1; i <= Q; i++){
		scanf("%d", &a);
		printf("%d\n", value[LCT.root(a)]);
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:101:29: 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:104:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^
synchronization.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
                  ^
synchronization.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16808 KB Output is correct
2 Correct 0 ms 16808 KB Output is correct
3 Correct 0 ms 16808 KB Output is correct
4 Correct 3 ms 16808 KB Output is correct
5 Correct 3 ms 16808 KB Output is correct
6 Correct 0 ms 16808 KB Output is correct
7 Correct 9 ms 17204 KB Output is correct
8 Correct 13 ms 17204 KB Output is correct
9 Correct 16 ms 17204 KB Output is correct
10 Correct 206 ms 20108 KB Output is correct
11 Correct 209 ms 20108 KB Output is correct
12 Correct 156 ms 24536 KB Output is correct
13 Correct 113 ms 20524 KB Output is correct
14 Correct 119 ms 20108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 22468 KB Output is correct
2 Correct 79 ms 22300 KB Output is correct
3 Correct 56 ms 24540 KB Output is correct
4 Correct 79 ms 24536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16808 KB Output is correct
2 Correct 0 ms 16808 KB Output is correct
3 Correct 0 ms 16808 KB Output is correct
4 Correct 3 ms 16808 KB Output is correct
5 Correct 0 ms 16808 KB Output is correct
6 Correct 0 ms 16808 KB Output is correct
7 Correct 16 ms 17416 KB Output is correct
8 Correct 196 ms 24536 KB Output is correct
9 Correct 193 ms 24540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 24540 KB Output is correct
2 Correct 123 ms 24508 KB Output is correct
3 Correct 109 ms 24536 KB Output is correct
4 Correct 133 ms 24536 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16808 KB Output is correct
2 Correct 0 ms 16808 KB Output is correct
3 Correct 0 ms 16808 KB Output is correct
4 Correct 0 ms 16808 KB Output is correct
5 Correct 3 ms 16808 KB Output is correct
6 Correct 13 ms 17204 KB Output is correct
7 Correct 306 ms 20108 KB Output is correct
8 Correct 203 ms 24540 KB Output is correct
9 Correct 209 ms 20524 KB Output is correct
10 Correct 259 ms 20108 KB Output is correct
11 Correct 129 ms 22468 KB Output is correct
12 Correct 133 ms 22472 KB Output is correct
13 Correct 103 ms 24540 KB Output is correct