oj.uz

Submission #594944

# Submission time Handle Problem Language Result Execution time Memory
594944 2022-07-13T07:33:38 Z 8e7 Parachute rings (IOI12_rings) C++17
17 / 100
 1524 ms 134916 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second

struct DSU{
	int par[maxn], siz[maxn];
	void init(int n){
		for (int i = 1;i <= n;i++) par[i] = i, siz[i] = 1;
	}
	int find(int a){
		return a == par[a] ? a : (par[a] = find(par[a]));
	}
	bool Union(int a, int b){
		a = find(a), b = find(b);
		if (a == b) return 0;
		if (siz[a] < siz[b]) swap(a, b);
		par[b] = a;
		siz[a] += siz[b];
		return 1;
	}
};
struct graph{ //maintaining a graph of nodes with deg <= 2
	DSU d;
	int deg[maxn];
	int cycle = 0, ignore = -1, count = 0;
	bool good = 1;
	int maxdeg = 0;
	void addedge(int u, int v){
		if (u == ignore || v == ignore) return;
		deg[u]++, deg[v]++;
		maxdeg = max(maxdeg, max(deg[u], deg[v]));
		if (maxdeg > 2) {
			good = 0;
			return;
		}
		if (!d.Union(u, v)) {
			cycle++;	
			if (cycle > 1) good = 0;
			else count = d.siz[d.find(u)];
		}	
	}	
} g;
vector<int> adj[maxn];
vector<pii> ed;
int N;
void Init(int N_) {
	N = N_;
	g.d.init(N);
}
graph cand[4];
int idx = 0;
void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
	ed.push_back({A, B});
	if (g.maxdeg < 3) {
		g.addedge(A, B);
		if (g.maxdeg >= 3) {
			if (g.deg[B] >= 3) swap(A, B);
			adj[A].push_back(A);
			for (int i:adj[A]) {
				graph &tmp = cand[idx++];
				tmp.d.init(N);
				tmp.ignore = i;
				for (auto p:ed) tmp.addedge(p.ff, p.ss);
			}
			adj[A].pop_back();
		}
	} else {
		for (auto &t:cand){
			t.addedge(A, B);	
		}
	}
}

int CountCritical() {
	if (g.good) {
		if (g.cycle == 1) return g.count;
		else return N;
	} else {
		int ret = 0;
		for (int t = 0;t < idx;t++) {
			if (cand[t].good && cand[t].cycle == 0) ret++;
		}
		return ret;
	}
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24260 KB Output is correct
3 Correct 17 ms 24500 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 15 ms 23980 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 55880 KB Output is correct
2 Correct 952 ms 112712 KB Output is correct
3 Correct 902 ms 129504 KB Output is correct
4 Correct 997 ms 86816 KB Output is correct
5 Correct 1018 ms 88044 KB Output is correct
6 Correct 985 ms 86228 KB Output is correct
7 Correct 821 ms 128384 KB Output is correct
8 Correct 1345 ms 127884 KB Output is correct
9 Correct 1524 ms 134916 KB Output is correct
10 Correct 680 ms 85128 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24260 KB Output is correct
3 Correct 17 ms 24500 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 15 ms 23980 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24260 KB Output is correct
3 Correct 17 ms 24500 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 15 ms 23980 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24260 KB Output is correct
3 Correct 17 ms 24500 KB Output is correct
4 Correct 14 ms 23812 KB Output is correct
5 Correct 15 ms 23980 KB Output is correct
6 Incorrect 15 ms 24148 KB Output isn't correct
7 Halted 0 ms 0 KB -