oj.uz

Submission #382372

# Submission time Handle Problem Language Result Execution time Memory
382372 2021-03-27T07:45:36 Z Keshi Parachute rings (IOI12_rings) C++17
20 / 100
 1435 ms 207512 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 5100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, m, t, cntdor, szdor, cnt3, cnt4;
pll e[maxn];

struct gr{
	ll x, a[maxn];
	bool ok;
	gr(ll y = 0){
		x = y;
		ok = 1;
		return;
	}
	void add(ll v, ll u){
		//cout << "! " << x << "\n";
		//cout << " add " << v << " " << u << "\n";
		if(v == x || u == x) return;
		ll av = a[v], au = a[u];
		if(av == u || av == -1 || au == -1){
			//cout << " --- fail ---- \n";
			ok = 0;
			return;
		}
		a[v] = -1;
		a[u] = -1;
		a[av] = au;
		a[au] = av;
		//for(ll i = 0; i < n; i++){
		//	cout << a[i] << " ";
		//}
		//cout << "\n----------\n";
		return;
	}
};

vector<ll> g[maxn];
bool ride, done[maxn];
ll dsu[maxn], sz[maxn], dr[maxn];
gr d[maxn];

ll par(ll v){
	if(dsu[v] != v) dsu[v] = par(dsu[v]);
	return dsu[v];
}

ll Union(ll v, ll u){
	v = par(v);
	u = par(u);
	if(v == u){
		if(dr[v]) return 0;
		dr[v] = 1;
		return sz[v];
	}
	if(sz[v] < sz[u]) swap(v, u);
	dsu[u] = v;
	sz[v] += sz[u];
	return 0;
}

void Do(ll v){
	if(done[v]) return;
	//cout << "# " << t << " -> " << v << "\n";
	done[v] = 1;
	cnt3++;
	d[t].x = v;
	d[t].ok = 1;
	for(ll i = 0; i < n; i++){
		d[t].a[i] = i;
	}
	for(ll i = 0; i < m; i++){
		d[t].add(e[i].F, e[i].S);
	}
	t++;
	return;
}
void Init(int N){
	n = N;
	for(ll i = 0; i < n; i++){
		Do(i);
	}
}
void Link(int A, int B){
	g[A].pb(B);
	g[B].pb(A);
	if(Sz(g[A]) == 3 && cnt3 < 4){
		Do(A);
		for(ll u : g[A]){
			Do(u);
		}
	}
	if(Sz(g[B]) == 3 && cnt3 < 4){
		Do(B);
		for(ll u : g[B]){
			Do(u);
		}
	}
	if(Sz(g[A]) == 4 && cnt4 < 1){
		Do(A);
		cnt3--;
		cnt4++;
	}
	if(Sz(g[B]) == 4 && cnt4 < 1){
		Do(B);
		cnt3--;
		cnt4++;
	}
	e[m++] = Mp(A, B);
	for(ll i = 0; i < t; i++){
		d[i].add(A, B);
	}
	ll x = Union(A, B);
	if(x){
		if(cntdor) ride = 1;
		cntdor++;
		szdor += x;
	}
	return;
}
int CountCritical(){
	if(ride) return 0;
	if(t == 0){
		if(cntdor == 0) return n;
		return szdor;
	}
	ll ans = 0;
	for(ll i = 0; i < t; i++){
		if(d[i].ok) ans++;
	}
	return ans;
}


/*int main(){
    fast_io;
    
    ll n, m;
    cin >> n >> m;
    Init(n);
    for(ll i = 0; i < m; i++){
    	ll x, y;
    	cin >> x;
    	if(x == -1){
    		cout << CountCritical() << "\n";
		}
		else{
			cin >> y;
			Link(x, y);
		}
	}
 
    return 0;
}*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21100 KB Output is correct
2 Correct 879 ms 87916 KB Output is correct
3 Correct 1249 ms 101100 KB Output is correct
4 Correct 29 ms 25068 KB Output is correct
5 Correct 430 ms 56372 KB Output is correct
6 Correct 1255 ms 100900 KB Output is correct
7 Correct 187 ms 100716 KB Output is correct
8 Correct 720 ms 88812 KB Output is correct
9 Correct 1255 ms 101100 KB Output is correct
10 Correct 1252 ms 101100 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1435 ms 207512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21100 KB Output is correct
2 Correct 879 ms 87916 KB Output is correct
3 Correct 1249 ms 101100 KB Output is correct
4 Correct 29 ms 25068 KB Output is correct
5 Correct 430 ms 56372 KB Output is correct
6 Correct 1255 ms 100900 KB Output is correct
7 Correct 187 ms 100716 KB Output is correct
8 Correct 720 ms 88812 KB Output is correct
9 Correct 1255 ms 101100 KB Output is correct
10 Correct 1252 ms 101100 KB Output is correct
11 Correct 1236 ms 100972 KB Output is correct
12 Execution timed out 72 ms 102380 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21100 KB Output is correct
2 Correct 879 ms 87916 KB Output is correct
3 Correct 1249 ms 101100 KB Output is correct
4 Correct 29 ms 25068 KB Output is correct
5 Correct 430 ms 56372 KB Output is correct
6 Correct 1255 ms 100900 KB Output is correct
7 Correct 187 ms 100716 KB Output is correct
8 Correct 720 ms 88812 KB Output is correct
9 Correct 1255 ms 101100 KB Output is correct
10 Correct 1252 ms 101100 KB Output is correct
11 Correct 1236 ms 100972 KB Output is correct
12 Execution timed out 72 ms 102380 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21100 KB Output is correct
2 Correct 879 ms 87916 KB Output is correct
3 Correct 1249 ms 101100 KB Output is correct
4 Correct 29 ms 25068 KB Output is correct
5 Correct 430 ms 56372 KB Output is correct
6 Correct 1255 ms 100900 KB Output is correct
7 Correct 187 ms 100716 KB Output is correct
8 Correct 720 ms 88812 KB Output is correct
9 Correct 1255 ms 101100 KB Output is correct
10 Correct 1252 ms 101100 KB Output is correct
11 Runtime error 1435 ms 207512 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -