답안 #36814 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36814	2017-12-14T20:22:52 Z	mohammad_kilani	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	2152 ms	113084 KB

rings

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n , comp[N], mx , adj[N] , ans = 0 , cycles = 0 , vis[N] , vi = 0 , comp2[4][N] , con1[4][N] , con2[4][N] , qu[N] , in[N] , idx = 0;
vector< int > g[N];
vector< pair<int,bool> > v;
vector< pair<int,int> > v2;

int Find(int u){
	if(u == comp[u]) return u;
	idx = 0 ;
	while(u != comp[u]){
		in[idx++] = u;
		u = comp[u];
	}
	while(idx > 0){
		idx--;
		comp[in[idx]] = u;
	}
	return u;
}

int Find2(int u,int i){
	if(u == comp2[i][u]) return u;
	idx = 0;
	while(u != comp2[i][u]){
		in[idx++] = u;
		u = comp2[i][u];
	}
	while(idx > 0){
		idx--;
		comp2[i][in[idx]] = u;
	}
	return u;
}

void Init(int N_) {
  n = N_;
  ans = n ;
  for(int i=0;i<n;i++) 
  	comp[i] = i;
  mx = 0 ;
  cycles = 0 ;
}


void DFS(int node,int prnt,int last){
	while(true){
		ans++;
		if(node == last) return;
		for(int i=0;i<(int)g[node].size();i++){
			if(g[node][i] != prnt){
				prnt = node;
				node = g[node][i];
				break;
			}
		}
	}
}

void DFS2(int node,int cant,int cur,int cnt){
	int st = 0 , en = 1 , num = 0;
	qu[st] = node;
	vis[node] = vi;
	while(st < en){
		node = qu[st++];
		comp2[cur][node] = cnt;
		num = 0 ;
		for(int i=0;i<(int)g[node].size();i++){
			num += (g[node][i] != cant);
			if(vis[g[node][i]] == vi || g[node][i] == cant) continue;
			qu[en++] = g[node][i];
			vis[g[node][i]] = vi;
		}
		if(num < 2){
			if(con1[cur][cnt] == -1) con1[cur][cnt] = node; else con2[cur][cnt] = node;
		}
	}
}

void make(int u){
	v.push_back(make_pair(u,true));
	for(int i=0;i<(int)g[u].size();i++){
		v.push_back(make_pair(g[u][i],true));
	}
	ans = 0 ;
	for(int i=0;i<(int)v.size();i++){
		vi++;
		for(int j=0;j<n;j++){
			if(j == v[i].first || vis[j] == vi) continue;
			con1[i][j] = con2[i][j] = -1;
			DFS2(j,v[i].first,i,j);
			if(con1[i][j] == -1){
				v[i].second = false;
				break;
			}
			if(con2[i][j] == -1) con2[i][j] = con1[i][j];
		}
		ans += v[i].second;
	}
}

void Link(int a, int b) {
	if(ans == 0) return;
	if(mx < 3){
		int u = Find(a);
		int v = Find(b);
		adj[a]++;
		adj[b]++;
		g[a].push_back(b);
		g[b].push_back(a);
		if(adj[a] == 3){
			mx = 3;
			make(a);
			return ;
		}
		if(adj[b] == 3){
			mx = 3;
			make(b);
			return;
		}
		if(u == v){
			if(cycles > 0){
				ans = 0;
				return ;
			}
			cycles++;
			ans = 0 ;
			DFS(a,b,b);
		}
		else{
			comp[u] = v;
		}
		return ;
	}
	for(int i=0;i<(int)v.size();i++){
		if(v[i].second == false) continue;
		if(a == v[i].first || b == v[i].first){
			adj[v[i].first]++;
			if(adj[v[i].first] > 3 && v.size() > 1){
				int cur = v[i].first;
				ans = 1;
				v.clear();
				v.push_back(make_pair(cur,1));
				break;
			}
			continue;
		}
		int u = Find2(comp2[i][a],i);
		int vv = Find2(comp2[i][b],i);
		if(u == vv){
			v[i].second = false;
			ans--;
			continue;
		}
		if(a != con1[i][u] && a != con2[i][u]){
			v[i].second = false;
			ans--;
			continue;
		}
		if(b != con1[i][vv] && b != con2[i][vv]){
			v[i].second = false;
			ans--;
			continue;
		}
		comp2[i][u] = vv;
		if(a == con1[i][u] && b == con1[i][vv]){
			con1[i][vv] = con2[i][u];
		}
		else if(a == con2[i][u] && b == con1[i][vv]){
			con1[i][vv] = con1[i][u];
		}
		else if(a == con1[i][u] && b == con2[i][vv]){
			con2[i][vv] = con2[i][u];
		}
		else if(a == con2[i][u] && b == con2[i][vv]){
			con2[i][vv] = con1[i][u];
		}
	}
}

int CountCritical() {
  return ans;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	24 ms	24460 KB	Output is correct
3	Correct	25 ms	24460 KB	Output is correct
4	Correct	28 ms	24460 KB	Output is correct
5	Correct	24 ms	24460 KB	Output is correct
6	Correct	24 ms	24460 KB	Output is correct
7	Correct	22 ms	24500 KB	Output is correct
8	Correct	24 ms	24500 KB	Output is correct
9	Correct	24 ms	24500 KB	Output is correct
10	Correct	24 ms	24500 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	440 ms	44592 KB	Output is correct
2	Correct	966 ms	85148 KB	Output is correct
3	Correct	393 ms	85148 KB	Output is correct
4	Correct	1160 ms	85148 KB	Output is correct
5	Correct	1180 ms	85148 KB	Output is correct
6	Correct	1320 ms	85148 KB	Output is correct
7	Correct	429 ms	85148 KB	Output is correct
8	Correct	1835 ms	105384 KB	Output is correct
9	Correct	2152 ms	113084 KB	Output is correct
10	Correct	788 ms	113084 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	24 ms	24460 KB	Output is correct
3	Correct	25 ms	24460 KB	Output is correct
4	Correct	28 ms	24460 KB	Output is correct
5	Correct	24 ms	24460 KB	Output is correct
6	Correct	24 ms	24460 KB	Output is correct
7	Correct	22 ms	24500 KB	Output is correct
8	Correct	24 ms	24500 KB	Output is correct
9	Correct	24 ms	24500 KB	Output is correct
10	Correct	24 ms	24500 KB	Output is correct
11	Correct	23 ms	113084 KB	Output is correct
12	Correct	28 ms	113084 KB	Output is correct
13	Correct	28 ms	113084 KB	Output is correct
14	Correct	23 ms	113084 KB	Output is correct
15	Correct	27 ms	113084 KB	Output is correct
16	Correct	26 ms	113084 KB	Output is correct
17	Correct	24 ms	113084 KB	Output is correct
18	Correct	27 ms	113084 KB	Output is correct
19	Correct	28 ms	113084 KB	Output is correct
20	Correct	27 ms	113084 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	24 ms	24460 KB	Output is correct
3	Correct	25 ms	24460 KB	Output is correct
4	Correct	28 ms	24460 KB	Output is correct
5	Correct	24 ms	24460 KB	Output is correct
6	Correct	24 ms	24460 KB	Output is correct
7	Correct	22 ms	24500 KB	Output is correct
8	Correct	24 ms	24500 KB	Output is correct
9	Correct	24 ms	24500 KB	Output is correct
10	Correct	24 ms	24500 KB	Output is correct
11	Correct	23 ms	113084 KB	Output is correct
12	Correct	28 ms	113084 KB	Output is correct
13	Correct	28 ms	113084 KB	Output is correct
14	Correct	23 ms	113084 KB	Output is correct
15	Correct	27 ms	113084 KB	Output is correct
16	Correct	26 ms	113084 KB	Output is correct
17	Correct	24 ms	113084 KB	Output is correct
18	Correct	27 ms	113084 KB	Output is correct
19	Correct	28 ms	113084 KB	Output is correct
20	Correct	27 ms	113084 KB	Output is correct
21	Correct	47 ms	113084 KB	Output is correct
22	Correct	56 ms	113084 KB	Output is correct
23	Correct	70 ms	113084 KB	Output is correct
24	Correct	61 ms	113084 KB	Output is correct
25	Correct	42 ms	113084 KB	Output is correct
26	Correct	67 ms	113084 KB	Output is correct
27	Correct	76 ms	113084 KB	Output is correct
28	Correct	57 ms	113084 KB	Output is correct
29	Correct	64 ms	113084 KB	Output is correct
30	Correct	93 ms	113084 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	24 ms	24460 KB	Output is correct
3	Correct	25 ms	24460 KB	Output is correct
4	Correct	28 ms	24460 KB	Output is correct
5	Correct	24 ms	24460 KB	Output is correct
6	Correct	24 ms	24460 KB	Output is correct
7	Correct	22 ms	24500 KB	Output is correct
8	Correct	24 ms	24500 KB	Output is correct
9	Correct	24 ms	24500 KB	Output is correct
10	Correct	24 ms	24500 KB	Output is correct
11	Correct	440 ms	44592 KB	Output is correct
12	Correct	966 ms	85148 KB	Output is correct
13	Correct	393 ms	85148 KB	Output is correct
14	Correct	1160 ms	85148 KB	Output is correct
15	Correct	1180 ms	85148 KB	Output is correct
16	Correct	1320 ms	85148 KB	Output is correct
17	Correct	429 ms	85148 KB	Output is correct
18	Correct	1835 ms	105384 KB	Output is correct
19	Correct	2152 ms	113084 KB	Output is correct
20	Correct	788 ms	113084 KB	Output is correct
21	Correct	23 ms	113084 KB	Output is correct
22	Correct	28 ms	113084 KB	Output is correct
23	Correct	28 ms	113084 KB	Output is correct
24	Correct	23 ms	113084 KB	Output is correct
25	Correct	27 ms	113084 KB	Output is correct
26	Correct	26 ms	113084 KB	Output is correct
27	Correct	24 ms	113084 KB	Output is correct
28	Correct	27 ms	113084 KB	Output is correct
29	Correct	28 ms	113084 KB	Output is correct
30	Correct	27 ms	113084 KB	Output is correct
31	Correct	47 ms	113084 KB	Output is correct
32	Correct	56 ms	113084 KB	Output is correct
33	Correct	70 ms	113084 KB	Output is correct
34	Correct	61 ms	113084 KB	Output is correct
35	Correct	42 ms	113084 KB	Output is correct
36	Correct	67 ms	113084 KB	Output is correct
37	Correct	76 ms	113084 KB	Output is correct
38	Correct	57 ms	113084 KB	Output is correct
39	Correct	64 ms	113084 KB	Output is correct
40	Correct	93 ms	113084 KB	Output is correct
41	Correct	254 ms	113084 KB	Output is correct
42	Correct	979 ms	113084 KB	Output is correct
43	Correct	307 ms	113084 KB	Output is correct
44	Correct	376 ms	113084 KB	Output is correct
45	Correct	588 ms	113084 KB	Output is correct
46	Correct	759 ms	113084 KB	Output is correct
47	Correct	1089 ms	113084 KB	Output is correct
48	Correct	363 ms	113084 KB	Output is correct
49	Correct	801 ms	113084 KB	Output is correct
50	Correct	813 ms	113084 KB	Output is correct
51	Correct	291 ms	113084 KB	Output is correct
52	Correct	340 ms	113084 KB	Output is correct
53	Correct	324 ms	113084 KB	Output is correct
54	Correct	1395 ms	113084 KB	Output is correct
55	Correct	652 ms	113084 KB	Output is correct

답안 #36814

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0