Submission #25496

#	Time	Username	Problem	Language	Result	Execution time	Memory
25496		zigui	Synchronization (JOI13_synchronization)	C++14	100 / 100	306 ms	24540 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40