oj.uz

Submission #223729

# Submission time Handle Problem Language Result Execution time Memory
223729 2020-04-16T08:58:16 Z staniewzki Parachute rings (IOI12_rings) C++17
0 / 100
 2642 ms 234744 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
 
template<class T> int size(T && a) { return (int) a.size(); }

struct Graph {
	vector<vector<int>> adj;
	vector<int> rep;

	int find(int x) {
		return rep[x] < 0 ? x : find(rep[x]);
	}

	vector<int> bicomp;
	int get_cycle() {
		return -rep[find(bicomp[0])];
	}

	void join(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) {
			bicomp.emplace_back(x);
			return;
		}
		rep[x] += rep[y];
		rep[y] = x;
	}

	int deg = 0;
	void add_edge(int a, int b) {
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
		deg = max(deg, size(adj[a]));
		deg = max(deg, size(adj[b]));
		join(a, b);
	}

	Graph(int n = 0) : adj(n), rep(n, -1) {}
};

int n;
Graph graph;
vector<Graph> without;

void Init(int N) {
	n = N;
	graph = Graph(n);
}

void Link(int A, int B) {
	if(graph.deg < 3) {
		graph.add_edge(A, B);
		if(graph.deg == 3) {
			if(size(graph.adj[A]) != 3)
				swap(A, B);

			vector<int> crit = {A};
			for(int u : graph.adj[A])
				crit.emplace_back(u);

			for(int x : crit) {
				without.emplace_back(n);
				auto &g = without.back();
				
				REP(v, n) for(int u : graph.adj[v]) {
					if(u < v && v != x && u != x)
						g.add_edge(v, u);		
				}
			}
		}
	}
	else {
		for(auto &g : without)
			g.add_edge(A, B);
	}
}

int CountCritical() {
	if(graph.deg < 3) {
		int bc = size(graph.bicomp);
		if(bc == 0) return n;
		if(bc == 1) return graph.get_cycle();
		return 0;
	}
	else {
		int ret = 0;
		for(auto &g : without) {
			if(size(g.bicomp) == 0 && g.deg < 3)
				ret++;
		}
		return ret;
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Incorrect 10 ms 1792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 37796 KB Output is correct
2 Incorrect 2642 ms 234744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Incorrect 10 ms 1792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Incorrect 10 ms 1792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Incorrect 10 ms 1792 KB Output isn't correct
4 Halted 0 ms 0 KB -