oj.uz

Submission #15162

# Submission time Handle Problem Language Result Execution time Memory
15162 2015-07-12T02:24:20 Z gs14004 Parachute rings (IOI12_rings) C++14
0 / 100
 1563 ms 102408 KB 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

vector<int> graph[1000005];
int n;

struct disj{
	int pa[1000005];
	int degcnt[1000005][6];
	vector<int> deg3[1000005];
	int cnt[1000005];
	int size[1000005];

	bool trash[1000005];
	bool bad[1000005];
	bool cycle[1000005];


	void init(int n){
		for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1;
	}

	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}

	void uni(int p, int q){
		p = find(p); q = find(q);
		if(p == q) return;
		pa[q] = p; find(q);
		for(int i=0; i<6; i++){
			degcnt[p][i] += degcnt[q][i];
		}
		size[p] += size[q];
		if(degcnt[p][5] || degcnt[p][4] > 1 || degcnt[p][3] > 4){
			trash[p] = 1;
			bad[p] = 0;
			cycle[p] = 0;
			deg3[p].clear();
			return;
		}
		else{
			for(auto &j : deg3[q]){
				deg3[p].push_back(j);
			}
			deg3[q].clear();
		}
		if(degcnt[p][3] || degcnt[p][4]){
			bad[p] = 1;
			cycle[p] = 0;
		}
		else if(degcnt[p][1] == 0){
			cycle[p] = 1;
		}
	}
}disj;

void Init(int N){
	n = N;	
	disj.init(n);
}

int deg[1000005];

void Link(int A, int B){
	graph[A].push_back(B);
	graph[B].push_back(A);
	deg[A]++, deg[B]++;
	int p = disj.find(A);
	if(deg[A] <= 5){
		disj.degcnt[p][deg[A]-1]--;
		disj.degcnt[p][deg[A]]++;
		if(deg[A] == 3){
			disj.deg3[p].push_back(A);
		}
	}
	p = disj.find(B);
	if(deg[B] <= 5){
		disj.degcnt[p][deg[B]-1]--;
		disj.degcnt[p][deg[B]]++;
		if(deg[B] == 3){
			disj.deg3[p].push_back(B);
		}
	}
	disj.uni(A,B);
}

bool vis[1000005];
queue<int> q;

bool tvis[1000005];

int solve(int x){
	memset(tvis,0,sizeof(tvis));
	tvis[x] = 1;
	int ret = 1;
	for(auto &i : graph[x]){
		deg[x]--;
		deg[i]--;
	}
	for(auto &i : graph[x]){
		if(tvis[i]) continue;
		tvis[i] = 1;
		q.push(i);
		int foundThree = 0, foundOne = 0, foundTwo = 0;
		while(!q.empty()){
			int qf = q.front();
			q.pop();
			if(deg[qf] >= 3) foundThree = 1;
			if(deg[qf] == 1) foundOne = 1;
			if(deg[qf] == 2) foundTwo = 1;
			for(auto &i : graph[qf]){
				if(!tvis[i]){
					tvis[i] = 1;
					q.push(i);
				}
			}
		}
		ret &= (!foundThree && !(foundTwo && !foundOne));
	}
	for(auto &i : graph[x]){
		deg[x]++;
		deg[i]++;
	}
	return ret;
}

int CountCritical(){
	memset(vis,0,sizeof(vis));
	int ret = 0, pos = -1;
	for(int i=0; i<n; i++){
		int p = disj.find(i);
		if(vis[p]) continue;
		vis[p] = 1;
		if(disj.trash[p]) return 0;
		else if(disj.cycle[p]){
			if(~pos) return 0;
			pos = p;
			ret = disj.size[p];
		}
		else if(disj.bad[p]){
			if(~pos) return 0;
			pos = p;
			ret = -1;
		}
		else{
			if(pos == -1) ret += disj.size[p];
		}
	}
	if(ret == -1){
		ret = 0;
	    pos = disj.deg3[pos][0];
		if(solve(pos)) ret++;
		for(auto &k : graph[pos]){
			if(solve(k)) ret++;
		}
	}
	return ret;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 48248 KB Output is correct
2 Correct 46 ms 49652 KB Output is correct
3 Incorrect 47 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 83260 KB Output is correct
2 Incorrect 1563 ms 102408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 48248 KB Output is correct
2 Correct 46 ms 49652 KB Output is correct
3 Incorrect 47 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 48248 KB Output is correct
2 Correct 46 ms 49652 KB Output is correct
3 Incorrect 47 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 48248 KB Output is correct
2 Correct 46 ms 49652 KB Output is correct
3 Incorrect 47 ms 49652 KB Output isn't correct
4 Halted 0 ms 0 KB -