oj.uz

Submission #390955

# Submission time Handle Problem Language Result Execution time Memory
390955 2021-04-17T12:37:02 Z AmineWeslati Parachute rings (IOI12_rings) C++14
100 / 100
 2061 ms 154672 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 1e6 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////


int N;
vi adj[MX];
vpi ed;

int phase1=1;

int deg[5][MX],nb_cy[5],cy[5],p[5][MX],rnk[5][MX],szz[5][MX];
vi crit(5,1);
vi critical={-1};

void Init(int N){
	::N=N; 
	memset(deg,0,sizeof(deg));
	memset(nb_cy,0,sizeof(nb_cy));
	FOR(i,0,5) FOR(u,0,N) p[i][u]=u;
	memset(rnk,0,sizeof(rnk));
	FOR(i,0,5) FOR(u,0,N) szz[i][u]=1;
}

int findSet(int i, int u){
	return p[i][u]==u ? u : p[i][u]=findSet(i,p[i][u]);
}


int f;
void join(int i, int u, int v){
	if(u==critical[i] || v==critical[i]) return;

	deg[i][u]++;
	deg[i][v]++;
	if(max(deg[i][u],deg[i][v])>=3){
		crit[i]=0;	
		f=0;
	}

	u=findSet(i,u),v=findSet(i,v);
	if(u==v){
		crit[i]=0;
		nb_cy[i]++;
		cy[i]=u;
		return; 
	}

	if(rnk[i][u]<rnk[i][v]) swap(u,v);
	if(rnk[i][u]==rnk[i][v]) rnk[i][u]++;
	p[i][v]=u;
	szz[i][u]+=szz[i][v];
}


void construct(int u){
	critical.pb(u);
	for(int v: adj[u]) critical.pb(v);

	FOR(i,1,5){
		int X=critical[i];
		for(auto it: ed){
			int u=it.fi,v=it.se;
			if(u!=X && v!=X)
				join(i,u,v);
		}
	}

}

void Link(int u, int v){
	ed.eb(u,v);
	adj[u].pb(v);
	adj[v].pb(u);

	f=1;
	join(0,u,v);
	
	if(phase1 && !f){
		phase1=0;
		if(deg[0][u]>=3) construct(u);
		else construct(v);
	}
	else if(!phase1){
		FOR(i,1,5) join(i,u,v);
	}
}


int CountCritical(){
	if(phase1){
		if(nb_cy[0]==0) return N; 
		if(nb_cy[0]>=2) return 0;
		return szz[0][cy[0]];
	}

	int ans=0;
	FOR(i,1,5) if(crit[i]) ans++;
	return ans; 
}

#ifdef LOCAL
int main() {
    boost; IO();

    int N; cin>>N;
    Init(N);
    
    int Q; cin>>Q;
    while(Q--){
    	int u; cin>>u;
    	if(u!=-1){
    		int v; cin>>v;
    		Link(u,v);
    	}
    	else cout << CountCritical() << endl;
    }

    return 0;
}
#endif
//Change your approach

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62916 KB Output is correct
2 Correct 39 ms 63328 KB Output is correct
3 Correct 38 ms 63440 KB Output is correct
4 Correct 35 ms 63056 KB Output is correct
5 Correct 37 ms 63172 KB Output is correct
6 Correct 37 ms 63436 KB Output is correct
7 Correct 37 ms 63188 KB Output is correct
8 Correct 37 ms 63268 KB Output is correct
9 Correct 38 ms 63376 KB Output is correct
10 Correct 37 ms 63460 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 103720 KB Output is correct
2 Correct 1669 ms 125548 KB Output is correct
3 Correct 2048 ms 136668 KB Output is correct
4 Correct 1251 ms 141288 KB Output is correct
5 Correct 1296 ms 154672 KB Output is correct
6 Correct 1233 ms 152684 KB Output is correct
7 Correct 1946 ms 147960 KB Output is correct
8 Correct 1919 ms 148848 KB Output is correct
9 Correct 2061 ms 154440 KB Output is correct
10 Correct 839 ms 151636 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62916 KB Output is correct
2 Correct 39 ms 63328 KB Output is correct
3 Correct 38 ms 63440 KB Output is correct
4 Correct 35 ms 63056 KB Output is correct
5 Correct 37 ms 63172 KB Output is correct
6 Correct 37 ms 63436 KB Output is correct
7 Correct 37 ms 63188 KB Output is correct
8 Correct 37 ms 63268 KB Output is correct
9 Correct 38 ms 63376 KB Output is correct
10 Correct 37 ms 63460 KB Output is correct
11 Correct 40 ms 63452 KB Output is correct
12 Correct 42 ms 63960 KB Output is correct
13 Correct 41 ms 63960 KB Output is correct
14 Correct 40 ms 63636 KB Output is correct
15 Correct 40 ms 63956 KB Output is correct
16 Correct 40 ms 63920 KB Output is correct
17 Correct 41 ms 63844 KB Output is correct
18 Correct 43 ms 64452 KB Output is correct
19 Correct 40 ms 63972 KB Output is correct
20 Correct 42 ms 63940 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62916 KB Output is correct
2 Correct 39 ms 63328 KB Output is correct
3 Correct 38 ms 63440 KB Output is correct
4 Correct 35 ms 63056 KB Output is correct
5 Correct 37 ms 63172 KB Output is correct
6 Correct 37 ms 63436 KB Output is correct
7 Correct 37 ms 63188 KB Output is correct
8 Correct 37 ms 63268 KB Output is correct
9 Correct 38 ms 63376 KB Output is correct
10 Correct 37 ms 63460 KB Output is correct
11 Correct 40 ms 63452 KB Output is correct
12 Correct 42 ms 63960 KB Output is correct
13 Correct 41 ms 63960 KB Output is correct
14 Correct 40 ms 63636 KB Output is correct
15 Correct 40 ms 63956 KB Output is correct
16 Correct 40 ms 63920 KB Output is correct
17 Correct 41 ms 63844 KB Output is correct
18 Correct 43 ms 64452 KB Output is correct
19 Correct 40 ms 63972 KB Output is correct
20 Correct 42 ms 63940 KB Output is correct
21 Correct 57 ms 66556 KB Output is correct
22 Correct 69 ms 68540 KB Output is correct
23 Correct 79 ms 70172 KB Output is correct
24 Correct 122 ms 69336 KB Output is correct
25 Correct 52 ms 67424 KB Output is correct
26 Correct 107 ms 70140 KB Output is correct
27 Correct 86 ms 70660 KB Output is correct
28 Correct 130 ms 70856 KB Output is correct
29 Correct 94 ms 69312 KB Output is correct
30 Correct 105 ms 71812 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62916 KB Output is correct
2 Correct 39 ms 63328 KB Output is correct
3 Correct 38 ms 63440 KB Output is correct
4 Correct 35 ms 63056 KB Output is correct
5 Correct 37 ms 63172 KB Output is correct
6 Correct 37 ms 63436 KB Output is correct
7 Correct 37 ms 63188 KB Output is correct
8 Correct 37 ms 63268 KB Output is correct
9 Correct 38 ms 63376 KB Output is correct
10 Correct 37 ms 63460 KB Output is correct
11 Correct 502 ms 103720 KB Output is correct
12 Correct 1669 ms 125548 KB Output is correct
13 Correct 2048 ms 136668 KB Output is correct
14 Correct 1251 ms 141288 KB Output is correct
15 Correct 1296 ms 154672 KB Output is correct
16 Correct 1233 ms 152684 KB Output is correct
17 Correct 1946 ms 147960 KB Output is correct
18 Correct 1919 ms 148848 KB Output is correct
19 Correct 2061 ms 154440 KB Output is correct
20 Correct 839 ms 151636 KB Output is correct
21 Correct 40 ms 63452 KB Output is correct
22 Correct 42 ms 63960 KB Output is correct
23 Correct 41 ms 63960 KB Output is correct
24 Correct 40 ms 63636 KB Output is correct
25 Correct 40 ms 63956 KB Output is correct
26 Correct 40 ms 63920 KB Output is correct
27 Correct 41 ms 63844 KB Output is correct
28 Correct 43 ms 64452 KB Output is correct
29 Correct 40 ms 63972 KB Output is correct
30 Correct 42 ms 63940 KB Output is correct
31 Correct 57 ms 66556 KB Output is correct
32 Correct 69 ms 68540 KB Output is correct
33 Correct 79 ms 70172 KB Output is correct
34 Correct 122 ms 69336 KB Output is correct
35 Correct 52 ms 67424 KB Output is correct
36 Correct 107 ms 70140 KB Output is correct
37 Correct 86 ms 70660 KB Output is correct
38 Correct 130 ms 70856 KB Output is correct
39 Correct 94 ms 69312 KB Output is correct
40 Correct 105 ms 71812 KB Output is correct
41 Correct 275 ms 96164 KB Output is correct
42 Correct 845 ms 122008 KB Output is correct
43 Correct 369 ms 106664 KB Output is correct
44 Correct 1357 ms 146156 KB Output is correct
45 Correct 1412 ms 137444 KB Output is correct
46 Correct 834 ms 139248 KB Output is correct
47 Correct 1115 ms 140716 KB Output is correct
48 Correct 856 ms 127464 KB Output is correct
49 Correct 826 ms 143564 KB Output is correct
50 Correct 899 ms 142640 KB Output is correct
51 Correct 467 ms 103900 KB Output is correct
52 Correct 1160 ms 130524 KB Output is correct
53 Correct 872 ms 128040 KB Output is correct
54 Correct 1738 ms 137720 KB Output is correct
55 Correct 2013 ms 144208 KB Output is correct