oj.uz

Submission #389828

# Submission time Handle Problem Language Result Execution time Memory
389828 2021-04-14T15:06:48 Z AmineWeslati Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 108064 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],critical,deg(MX,0),cy,p(MX),rnk(MX);

void Init(int N){
	::N=N; 
	FOR(i,0,N){
		p[i]=i,rnk[i]=0;
		critical.pb(i);
	}
}
	
int findSet(int u){
	return p[u]==u ? u : p[u]=findSet(p[u]);
}
void joinSet(int u, int v){
	u=findSet(u),v=findSet(v);
	if(u==v) return; 
	if(rnk[u]<rnk[v]) swap(u,v);
	if(rnk[u]==rnk[v]) rnk[u]++;
	p[v]=u;
}

vi vis(MX,0);
void inter(vi vec){
	for(int x: vec) vis[x]=1;

	vi nw; 
	for(int x: critical) if(vis[x]) 
		nw.pb(x);
	critical.assign(all(nw));

	for(int x: vec) vis[x]=0;
}


vi par;
void dfs(int u){
	for(int v: adj[u]) if(par[v]==-1){
		par[v]=u; 
		dfs(v);
	}
}

void find_cy(int u, int v){
	cy.clear();

	par.assign(N,-1);
	par[u]=u;
	dfs(u);

	while(1){
		cy.pb(v);
		if(v==u) break;
		v=par[v];
	}
}

void Link(int u, int v){
	if(!sz(critical)) return;

	deg[u]++; deg[v]++;

	if(deg[u]<4 && deg[v]<4 && findSet(u)==findSet(v)){
		find_cy(u,v);
		inter(cy);
	}

	adj[u].pb(v);
	adj[v].pb(u);
	
	if(deg[u]>=4)
		inter(vi{u});
	if(deg[v]>=4)
		inter(vi{v});

	if(deg[u]==3){
		vi vec; 
		vec.assign(all(adj[u]));
		vec.pb(u);
		inter(vec);
	}
	
	if(deg[v]==3){
		vi vec; 
		vec.assign(all(adj[v]));
		vec.pb(v);
		inter(vec);
	}

	joinSet(u,v);
}

int CountCritical(){
	return sz(critical);
}

#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 

/*

5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
3
3
3
3
3
3
3
2
2
2
0
0
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 27 ms 39552 KB Output is correct
3 Correct 26 ms 39628 KB Output is correct
4 Correct 28 ms 39468 KB Output is correct
5 Correct 26 ms 39612 KB Output is correct
6 Correct 27 ms 39804 KB Output is correct
7 Correct 24 ms 39444 KB Output is correct
8 Correct 30 ms 39628 KB Output is correct
9 Correct 27 ms 39628 KB Output is correct
10 Correct 26 ms 39676 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 57820 KB Output is correct
2 Correct 1063 ms 67492 KB Output is correct
3 Correct 301 ms 43812 KB Output is correct
4 Correct 1346 ms 78568 KB Output is correct
5 Correct 1344 ms 79896 KB Output is correct
6 Correct 1469 ms 108064 KB Output is correct
7 Correct 396 ms 44008 KB Output is correct
8 Correct 1244 ms 72536 KB Output is correct
9 Correct 1325 ms 74708 KB Output is correct
10 Correct 946 ms 77068 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 27 ms 39552 KB Output is correct
3 Correct 26 ms 39628 KB Output is correct
4 Correct 28 ms 39468 KB Output is correct
5 Correct 26 ms 39612 KB Output is correct
6 Correct 27 ms 39804 KB Output is correct
7 Correct 24 ms 39444 KB Output is correct
8 Correct 30 ms 39628 KB Output is correct
9 Correct 27 ms 39628 KB Output is correct
10 Correct 26 ms 39676 KB Output is correct
11 Correct 26 ms 39660 KB Output is correct
12 Correct 28 ms 39820 KB Output is correct
13 Correct 29 ms 39884 KB Output is correct
14 Correct 135 ms 39644 KB Output is correct
15 Correct 177 ms 39880 KB Output is correct
16 Correct 29 ms 39884 KB Output is correct
17 Correct 28 ms 39628 KB Output is correct
18 Correct 27 ms 39716 KB Output is correct
19 Correct 30 ms 39896 KB Output is correct
20 Correct 30 ms 39756 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 27 ms 39552 KB Output is correct
3 Correct 26 ms 39628 KB Output is correct
4 Correct 28 ms 39468 KB Output is correct
5 Correct 26 ms 39612 KB Output is correct
6 Correct 27 ms 39804 KB Output is correct
7 Correct 24 ms 39444 KB Output is correct
8 Correct 30 ms 39628 KB Output is correct
9 Correct 27 ms 39628 KB Output is correct
10 Correct 26 ms 39676 KB Output is correct
11 Correct 26 ms 39660 KB Output is correct
12 Correct 28 ms 39820 KB Output is correct
13 Correct 29 ms 39884 KB Output is correct
14 Correct 135 ms 39644 KB Output is correct
15 Correct 177 ms 39880 KB Output is correct
16 Correct 29 ms 39884 KB Output is correct
17 Correct 28 ms 39628 KB Output is correct
18 Correct 27 ms 39716 KB Output is correct
19 Correct 30 ms 39896 KB Output is correct
20 Correct 30 ms 39756 KB Output is correct
21 Correct 48 ms 40628 KB Output is correct
22 Correct 62 ms 41348 KB Output is correct
23 Correct 72 ms 42028 KB Output is correct
24 Execution timed out 4078 ms 41992 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39372 KB Output is correct
2 Correct 27 ms 39552 KB Output is correct
3 Correct 26 ms 39628 KB Output is correct
4 Correct 28 ms 39468 KB Output is correct
5 Correct 26 ms 39612 KB Output is correct
6 Correct 27 ms 39804 KB Output is correct
7 Correct 24 ms 39444 KB Output is correct
8 Correct 30 ms 39628 KB Output is correct
9 Correct 27 ms 39628 KB Output is correct
10 Correct 26 ms 39676 KB Output is correct
11 Correct 547 ms 57820 KB Output is correct
12 Correct 1063 ms 67492 KB Output is correct
13 Correct 301 ms 43812 KB Output is correct
14 Correct 1346 ms 78568 KB Output is correct
15 Correct 1344 ms 79896 KB Output is correct
16 Correct 1469 ms 108064 KB Output is correct
17 Correct 396 ms 44008 KB Output is correct
18 Correct 1244 ms 72536 KB Output is correct
19 Correct 1325 ms 74708 KB Output is correct
20 Correct 946 ms 77068 KB Output is correct
21 Correct 26 ms 39660 KB Output is correct
22 Correct 28 ms 39820 KB Output is correct
23 Correct 29 ms 39884 KB Output is correct
24 Correct 135 ms 39644 KB Output is correct
25 Correct 177 ms 39880 KB Output is correct
26 Correct 29 ms 39884 KB Output is correct
27 Correct 28 ms 39628 KB Output is correct
28 Correct 27 ms 39716 KB Output is correct
29 Correct 30 ms 39896 KB Output is correct
30 Correct 30 ms 39756 KB Output is correct
31 Correct 48 ms 40628 KB Output is correct
32 Correct 62 ms 41348 KB Output is correct
33 Correct 72 ms 42028 KB Output is correct
34 Execution timed out 4078 ms 41992 KB Time limit exceeded
35 Halted 0 ms 0 KB -