Submission #223740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223740	2020-04-16T09:21:20 Z	staniewzki	Parachute rings (IOI12_rings)	C++17	100 / 100	921 ms	60888 KB

rings

#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<int> rep, deg;
	int excluded = -1;

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

	int bicomp = -1;
	int get_cycle() {
		return -rep[find(bicomp)];
	}

	void join(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) {
			if(bicomp == -1) bicomp = x;
			else bicomp = -2;
			return;
		}
		if(rep[x] > rep[y])
			swap(x, y);
		rep[x] += rep[y];
		rep[y] = x;
	}

	int max_deg = 0;
	void add_edge(int a, int b) {
		if(a == excluded || b == excluded)
			return;
		max_deg |= 3 <= ++deg[a];
		max_deg |= 3 <= ++deg[b];
		join(a, b);
	}

	Graph(int n = 0, int e = -1) : rep(n, -1), deg(n), excluded(e) {}
};

int n;
vector<pair<int, int>> edges;
Graph graph;
vector<Graph> without;

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

void Link(int A, int B) {
	edges.emplace_back(A, B);
	if(!graph.max_deg) {
		graph.add_edge(A, B);
		if(graph.max_deg) {
			if(graph.deg[A] != 3)
				swap(A, B);

			vector<int> crit = {A};
			for(auto &[u, v] : edges) {
				if(u == A) crit.emplace_back(v);
				if(v == A) crit.emplace_back(u);
			}

			for(int x : crit) {
				without.emplace_back(n, x);
				for(auto &[u, v] : edges)
					without.back().add_edge(v, u);		
			}
		}
	}
	else {
		for(auto &g : without)
			g.add_edge(A, B);
	}
}

int CountCritical() {
	if(!graph.max_deg) {
		if(graph.bicomp == -1) return n;
		if(graph.bicomp == -2) return 0;
		return graph.get_cycle();
	}
	else {
		int ret = 0;
		for(auto &g : without) {
			if(g.bicomp == -1 && !g.max_deg)
				ret++;
		}
		return ret;
	}
}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	6 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	6 ms	640 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	8940 KB	Output is correct
2	Correct	675 ms	40288 KB	Output is correct
3	Correct	921 ms	52936 KB	Output is correct
4	Correct	476 ms	29676 KB	Output is correct
5	Correct	480 ms	29656 KB	Output is correct
6	Correct	475 ms	28884 KB	Output is correct
7	Correct	893 ms	59048 KB	Output is correct
8	Correct	784 ms	56920 KB	Output is correct
9	Correct	752 ms	60888 KB	Output is correct
10	Correct	412 ms	28376 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	6 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	6 ms	640 KB	Output is correct
11	Correct	8 ms	640 KB	Output is correct
12	Correct	8 ms	896 KB	Output is correct
13	Correct	8 ms	1024 KB	Output is correct
14	Correct	7 ms	896 KB	Output is correct
15	Correct	8 ms	1408 KB	Output is correct
16	Correct	8 ms	768 KB	Output is correct
17	Correct	8 ms	1024 KB	Output is correct
18	Correct	8 ms	1536 KB	Output is correct
19	Correct	8 ms	768 KB	Output is correct
20	Correct	9 ms	976 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	6 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	6 ms	640 KB	Output is correct
11	Correct	8 ms	640 KB	Output is correct
12	Correct	8 ms	896 KB	Output is correct
13	Correct	8 ms	1024 KB	Output is correct
14	Correct	7 ms	896 KB	Output is correct
15	Correct	8 ms	1408 KB	Output is correct
16	Correct	8 ms	768 KB	Output is correct
17	Correct	8 ms	1024 KB	Output is correct
18	Correct	8 ms	1536 KB	Output is correct
19	Correct	8 ms	768 KB	Output is correct
20	Correct	9 ms	976 KB	Output is correct
21	Correct	20 ms	1536 KB	Output is correct
22	Correct	27 ms	2048 KB	Output is correct
23	Correct	36 ms	2304 KB	Output is correct
24	Correct	38 ms	4984 KB	Output is correct
25	Correct	19 ms	4736 KB	Output is correct
26	Correct	38 ms	5748 KB	Output is correct
27	Correct	37 ms	3316 KB	Output is correct
28	Correct	42 ms	5884 KB	Output is correct
29	Correct	33 ms	5376 KB	Output is correct
30	Correct	40 ms	3196 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	6 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	512 KB	Output is correct
6	Correct	6 ms	640 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	6 ms	640 KB	Output is correct
11	Correct	206 ms	8940 KB	Output is correct
12	Correct	675 ms	40288 KB	Output is correct
13	Correct	921 ms	52936 KB	Output is correct
14	Correct	476 ms	29676 KB	Output is correct
15	Correct	480 ms	29656 KB	Output is correct
16	Correct	475 ms	28884 KB	Output is correct
17	Correct	893 ms	59048 KB	Output is correct
18	Correct	784 ms	56920 KB	Output is correct
19	Correct	752 ms	60888 KB	Output is correct
20	Correct	412 ms	28376 KB	Output is correct
21	Correct	8 ms	640 KB	Output is correct
22	Correct	8 ms	896 KB	Output is correct
23	Correct	8 ms	1024 KB	Output is correct
24	Correct	7 ms	896 KB	Output is correct
25	Correct	8 ms	1408 KB	Output is correct
26	Correct	8 ms	768 KB	Output is correct
27	Correct	8 ms	1024 KB	Output is correct
28	Correct	8 ms	1536 KB	Output is correct
29	Correct	8 ms	768 KB	Output is correct
30	Correct	9 ms	976 KB	Output is correct
31	Correct	20 ms	1536 KB	Output is correct
32	Correct	27 ms	2048 KB	Output is correct
33	Correct	36 ms	2304 KB	Output is correct
34	Correct	38 ms	4984 KB	Output is correct
35	Correct	19 ms	4736 KB	Output is correct
36	Correct	38 ms	5748 KB	Output is correct
37	Correct	37 ms	3316 KB	Output is correct
38	Correct	42 ms	5884 KB	Output is correct
39	Correct	33 ms	5376 KB	Output is correct
40	Correct	40 ms	3196 KB	Output is correct
41	Correct	149 ms	11676 KB	Output is correct
42	Correct	379 ms	45796 KB	Output is correct
43	Correct	247 ms	42356 KB	Output is correct
44	Correct	575 ms	55896 KB	Output is correct
45	Correct	648 ms	56292 KB	Output is correct
46	Correct	394 ms	26200 KB	Output is correct
47	Correct	420 ms	26364 KB	Output is correct
48	Correct	399 ms	50616 KB	Output is correct
49	Correct	380 ms	26584 KB	Output is correct
50	Correct	393 ms	26196 KB	Output is correct
51	Correct	270 ms	37484 KB	Output is correct
52	Correct	492 ms	45652 KB	Output is correct
53	Correct	386 ms	49936 KB	Output is correct
54	Correct	693 ms	50392 KB	Output is correct
55	Correct	810 ms	54360 KB	Output is correct

Submission #223740

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0