oj.uz

답안 #36809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36809 2017-12-14T19:59:45 Z mohammad_kilani 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 2190 ms 113300 KB 
#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];
vector< int > g[N];
vector< pair<int,bool> > v;
vector< pair<int,int> > v2;

int Find(int u){
	return (u == comp[u] ? u : comp[u] = Find(comp[u]));
}

int Find2(int u,int i){
	if(u == comp2[i][u]) 
		return u;
	return comp2[i][u] = Find2(comp2[i][u],i);
}

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){
	ans++;
	if(node == last) return;
	for(int i=0;i<(int)g[node].size();i++){
		if(g[node][i] != prnt) DFS(g[node][i],node,last);
	}
}

void DFS2(int node,int cant,int cur,int cnt){
	vis[node] = vi;
	int num = 0 ;
	comp2[cur][node] = cnt;
	for(int i=0;i<(int)g[node].size();i++){
		int newnode = g[node][i];
		num += (newnode != cant);
		if(vis[newnode] == vi || newnode == cant) continue;
		DFS2(newnode,cant,cur,cnt);
	}
	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;
			v.erase(v.begin() + i);
			i--;
			ans--;
			continue;
		}
		if(a != con1[i][u] && a != con2[i][u]){
			v[i].second = false;
			v.erase(v.begin() + i);
			i--;
			ans--;
			continue;
		}
		if(b != con1[i][vv] && b != con2[i][vv]){
			v[i].second = false;
			v.erase(v.begin() + i);
			i--;
			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 22 ms 23772 KB Output is correct
2 Correct 30 ms 24444 KB Output is correct
3 Correct 23 ms 24444 KB Output is correct
4 Correct 25 ms 24444 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 26 ms 24444 KB Output is correct
7 Correct 28 ms 24584 KB Output is correct
8 Correct 23 ms 24584 KB Output is correct
9 Correct 25 ms 24604 KB Output is correct
10 Correct 25 ms 24604 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 443 ms 44480 KB Output is correct
2 Correct 1027 ms 85112 KB Output is correct
3 Correct 403 ms 85112 KB Output is correct
4 Correct 1289 ms 85112 KB Output is correct
5 Correct 1247 ms 85112 KB Output is correct
6 Correct 1326 ms 85148 KB Output is correct
7 Correct 403 ms 85148 KB Output is correct
8 Correct 1886 ms 105532 KB Output is correct
9 Incorrect 2190 ms 113300 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23772 KB Output is correct
2 Correct 30 ms 24444 KB Output is correct
3 Correct 23 ms 24444 KB Output is correct
4 Correct 25 ms 24444 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 26 ms 24444 KB Output is correct
7 Correct 28 ms 24584 KB Output is correct
8 Correct 23 ms 24584 KB Output is correct
9 Correct 25 ms 24604 KB Output is correct
10 Correct 25 ms 24604 KB Output is correct
11 Incorrect 23 ms 113300 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23772 KB Output is correct
2 Correct 30 ms 24444 KB Output is correct
3 Correct 23 ms 24444 KB Output is correct
4 Correct 25 ms 24444 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 26 ms 24444 KB Output is correct
7 Correct 28 ms 24584 KB Output is correct
8 Correct 23 ms 24584 KB Output is correct
9 Correct 25 ms 24604 KB Output is correct
10 Correct 25 ms 24604 KB Output is correct
11 Incorrect 23 ms 113300 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23772 KB Output is correct
2 Correct 30 ms 24444 KB Output is correct
3 Correct 23 ms 24444 KB Output is correct
4 Correct 25 ms 24444 KB Output is correct
5 Correct 24 ms 24444 KB Output is correct
6 Correct 26 ms 24444 KB Output is correct
7 Correct 28 ms 24584 KB Output is correct
8 Correct 23 ms 24584 KB Output is correct
9 Correct 25 ms 24604 KB Output is correct
10 Correct 25 ms 24604 KB Output is correct
11 Correct 443 ms 44480 KB Output is correct
12 Correct 1027 ms 85112 KB Output is correct
13 Correct 403 ms 85112 KB Output is correct
14 Correct 1289 ms 85112 KB Output is correct
15 Correct 1247 ms 85112 KB Output is correct
16 Correct 1326 ms 85148 KB Output is correct
17 Correct 403 ms 85148 KB Output is correct
18 Correct 1886 ms 105532 KB Output is correct
19 Incorrect 2190 ms 113300 KB Output isn't correct
20 Halted 0 ms 0 KB -