oj.uz

답안 #382372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382372 2021-03-27T07:45:36 Z Keshi 낙하산 고리들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -