oj.uz

Submission #36809

# Submission time Handle Problem Language Result Execution time Memory
36809 2017-12-14T19:59:45 Z mohammad_kilani Parachute rings (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -