oj.uz

Submission #382375

# Submission time Handle Problem Language Result Execution time Memory
382375 2021-03-27T07:50:21 Z Keshi Parachute rings (IOI12_rings) C++17
20 / 100
 1238 ms 101100 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;
}
void Link(int A, int B){
	g[A].pb(B);
	g[B].pb(A);
	if(Sz(g[A]) == 3 && cnt3 < 5){
		Do(A);
		for(ll u : g[A]){
			Do(u);
		}
	}
	if(Sz(g[B]) == 3 && cnt3 < 5){
		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(){
	for(ll i = 0; i < n; i++){
		Do(i);
	}
	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 12 ms 21100 KB Output is correct
2 Correct 185 ms 88044 KB Output is correct
3 Correct 278 ms 100972 KB Output is correct
4 Correct 22 ms 25068 KB Output is correct
5 Correct 94 ms 56428 KB Output is correct
6 Correct 276 ms 101008 KB Output is correct
7 Correct 85 ms 100716 KB Output is correct
8 Correct 178 ms 88940 KB Output is correct
9 Correct 270 ms 100972 KB Output is correct
10 Correct 272 ms 101100 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 42860 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 12 ms 21100 KB Output is correct
2 Correct 185 ms 88044 KB Output is correct
3 Correct 278 ms 100972 KB Output is correct
4 Correct 22 ms 25068 KB Output is correct
5 Correct 94 ms 56428 KB Output is correct
6 Correct 276 ms 101008 KB Output is correct
7 Correct 85 ms 100716 KB Output is correct
8 Correct 178 ms 88940 KB Output is correct
9 Correct 270 ms 100972 KB Output is correct
10 Correct 272 ms 101100 KB Output is correct
11 Correct 1238 ms 101096 KB Output is correct
12 Runtime error 84 ms 42860 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21100 KB Output is correct
2 Correct 185 ms 88044 KB Output is correct
3 Correct 278 ms 100972 KB Output is correct
4 Correct 22 ms 25068 KB Output is correct
5 Correct 94 ms 56428 KB Output is correct
6 Correct 276 ms 101008 KB Output is correct
7 Correct 85 ms 100716 KB Output is correct
8 Correct 178 ms 88940 KB Output is correct
9 Correct 270 ms 100972 KB Output is correct
10 Correct 272 ms 101100 KB Output is correct
11 Correct 1238 ms 101096 KB Output is correct
12 Runtime error 84 ms 42860 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21100 KB Output is correct
2 Correct 185 ms 88044 KB Output is correct
3 Correct 278 ms 100972 KB Output is correct
4 Correct 22 ms 25068 KB Output is correct
5 Correct 94 ms 56428 KB Output is correct
6 Correct 276 ms 101008 KB Output is correct
7 Correct 85 ms 100716 KB Output is correct
8 Correct 178 ms 88940 KB Output is correct
9 Correct 270 ms 100972 KB Output is correct
10 Correct 272 ms 101100 KB Output is correct
11 Runtime error 85 ms 42860 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -