oj.uz

Submission #119213

# Submission time Handle Problem Language Result Execution time Memory
119213 2019-06-20T16:39:59 Z ioilolcom Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 99540 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
int N;
vector<int> edges;
const int M=1e6+7;
set<int> adj[M];
int deg[M];
void Init(int N_) {
	N = N_;
}

void Link(int A, int B) {
	adj[A].insert(B);
	adj[B].insert(A);
	deg[A]++;
	deg[B]++;
}
vector<char> color;
bool dfs(int v) {
	color[v] = 1;
	for (int u : adj[v]) {
		if (color[u] == 0) {
			if (dfs(u))
				return true;
		} else if (color[u] == 1) {
			return true;
		}
	}
	color[v] = 2;
	return false;
}

bool cycle() {
	color.assign(N,-1);
	for(int x=0; x<N; x++) {
		if(color[x]) {
			continue;
		}
		if(dfs(x)) {
			return 1;
		}
	}
	return 0;
}
bool is(int x){
	vector<int> lol;
	for(int v:adj[x]) {
		lol.push_back(v);
		adj[x].erase(v);
		adj[v].erase(x);
		deg[v]--;
	}
	for(int v=0; v<N; v++) {
		if(v==x) {
			continue;
		}
		if(deg[v]>2) {
			return 0;
		}
	}
	if(cycle()) {
		return 0;
	}
	for(int v:lol) {
		deg[v]++;
		adj[x].insert(v);
		adj[v].insert(x);
	}
	return 1;
}
int CountCritical() {
	int ans=0;
	for(int x=0; x<N; x++) ans+=is(x);
	return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 47352 KB Output is correct
2 Incorrect 57 ms 47736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4037 ms 99540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 47352 KB Output is correct
2 Incorrect 57 ms 47736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 47352 KB Output is correct
2 Incorrect 57 ms 47736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 47352 KB Output is correct
2 Incorrect 57 ms 47736 KB Output isn't correct
3 Halted 0 ms 0 KB -