oj.uz

Submission #752023

# Submission time Handle Problem Language Result Execution time Memory
752023 2023-06-02T05:35:34 Z minhcool Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 228996 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int n;
vector<int> Adj[N]; 
vector<ii> edges;
 
int deg[N], mx_deg;
set<ii> se;
 
int cur_ans = 0;
 
int szz[N], rtt[N];
 
void Init(int N_) {
	n = N_;
	for(int i = 1; i <= n; i++){
		szz[i] = 1, rtt[i] = i;	
	}
	cur_ans = n;
}
 
int cnt;
vector<int> candidates;
 
int deg2[N][8], mxdeg[8];
 
bool out[N];
 
int sz[N][8], rt[N][8];
 
void init(int ind){
	for(int i = 1; i <= n; i++){
		sz[i][ind] = 1, rt[i][ind] = i;
		deg2[i][ind] = 0;
	}
	mxdeg[ind] = 0;
	out[ind] = 0;
}
 
int root(int x, int ind){
	return (x == rt[x][ind] ? x : rt[x][ind] = root(rt[x][ind], ind));
}
 
bool merge(int x, int y, int ind){
	x = root(x, ind), y = root(y, ind);
	if(x == y) return 0;
	if(sz[x][ind] < sz[y][ind]) swap(x, y);
	sz[x][ind] += sz[y][ind];
	rt[y][ind] = x;
	return 1;
}
 
void add_edge(int x, int y, int ind){
	if(x == candidates[ind - 1] || y == candidates[ind - 1]) return;
	deg2[x][ind]++, deg2[y][ind]++;
	mxdeg[ind] = max(mxdeg[ind], deg2[x][ind]);
	mxdeg[ind] = max(mxdeg[ind], deg2[y][ind]);
	out[ind] |= (!merge(x, y, ind));
	out[ind] |= (mxdeg[ind] >= 3);
}
 
 
int roott(int x){
	return (x == rtt[x] ? x : rtt[x] = roott(rtt[x]));
}
 
bool mergee(int x, int y){
	x = roott(x), y = roott(y);
	if(x == y) return 0;
	if(szz[x] < szz[y]) swap(x, y);
	szz[x] += szz[y];
	rtt[y] = x;
	return 1;
}
 
int tol_cyc = 0;
 
int d[N];
 
vector<int> Ad[N];
 
void dfs(int u, int p){
	for(auto v : Adj[u]){
		if(v == p) continue;
		d[v] = d[u] + 1;
		dfs(v, u);
	}
}
 
void Link(int A, int B) {
	A++, B++;
	//Adj[A].pb(B);
	//Adj[B].pb(A);
	Ad[A].pb(B);
	Ad[B].pb(A);
	edges.pb({A, B});
	int old = mx_deg;
	se.erase({deg[A], A});
	se.erase({deg[B], B});
	deg[A]++;
	deg[B]++;
	se.insert({deg[A], A});
	se.insert({deg[B], B});
	mx_deg = max(mx_deg, deg[A]);
	mx_deg = max(mx_deg, deg[B]);
	if(mx_deg <= 2){
        if(tol_cyc >= 2) return;
		int lst = tol_cyc;
		tol_cyc += (!mergee(A, B));
		if(tol_cyc == 2) cur_ans = 0;
		else if(!tol_cyc) cur_ans = n;
		else{
			if(lst == 1) return;
			for(int i = 0; (i + 1) < edges.size(); i++){
				Adj[edges[i].fi].pb(edges[i].se);
				Adj[edges[i].se].pb(edges[i].fi);
			}
			dfs(A, A);
			cur_ans = d[B] + 1;
		}
	}
	else if(mx_deg == 3){
	//	cout << "OK " << cnt << "\n";
		int counter = 0;
		set<ii>::iterator it = se.end();
		while(it != se.begin()){
			it--;
			if((*it).fi < 3) break;
            if(counter > 4) break;
			counter++;
 		}
		if(counter > 4){
			cur_ans = 0;
			return;
		}
		int lst_cnt = cnt;
		if(deg[A] >= 3){
			bool ck = 1;
			for(auto it : candidates) ck &= (it != A);
			if(ck){
				cnt++;
				init(cnt);
				candidates.pb(A);
				for(auto it : edges) add_edge(it.fi, it.se, cnt);
			}
			for(auto it : Ad[A]){		
				bool ck = 1;
				for(auto it2 : candidates) ck &= (it != it2);
				int cn = 0;
				for(auto it2 : Ad[it]) cn += (deg[it2] >= 3);
				ck &= (cn == counter); 
				if(ck){
					cnt++;
					init(cnt);
					candidates.pb(it);
					for(auto it2 : edges) add_edge(it2.fi, it2.se, cnt);
				}
			}
		}
		if(deg[B] >= 3){
			bool ck = 1;
			for(auto it : candidates) ck &= (it != B);
			if(ck){
				cnt++;
				init(cnt);
				candidates.pb(B);
				for(auto it : edges) add_edge(it.fi, it.se, cnt);
			}
			for(auto it : Ad[B]){		
				bool ck = 1;
				for(auto it2 : candidates) ck &= (it != it2);
				int cn = 0;
				for(auto it2 : Ad[it]) cn += (deg[it2] >= 3);
				ck &= (cn == counter); 
				if(ck){
					cnt++;
					init(cnt);
					candidates.pb(it);
					for(auto it2 : edges) add_edge(it2.fi, it2.se, cnt);
				}
			}
		}
	//	exit(0);
		for(int i = 1; i <= lst_cnt; i++) add_edge(A, B, i);
		cur_ans = 0;
		for(int i = 1; i <= cnt; i++) cur_ans += (!out[i]);
	}
	else{
		//cout << "OK\n";
		if(old < 4){
			candidates.clear();
			cnt = 0;
		}
        else{
          if(cnt >= 2) return;
		}
		if(deg[A] >= 4){
			bool ck = 1;
			for(auto it : candidates) ck &= (it != A);
			if(ck){
				cnt++;
				candidates.pb(A);
			}
		}
		if(deg[B] >= 4){
			bool ck = 1;
			for(auto it : candidates) ck &= (it != B);
			if(ck){
				cnt++;
				candidates.pb(B);
			}
		}
	//	cout << cnt << "\n";
		if(cnt >= 2){
			cur_ans = 0;
			return;
		}
		if(old < 4){// build new graph
			init(1);
			assert(cnt == 1);
			for(auto it : edges) add_edge(it.fi, it.se, 1);
		}
		else{
			add_edge(A, B, 1);
		}
		cur_ans = (!out[1]);
	}
}
 
int CountCritical() {
	return cur_ans;
}
 
/*
void process(){
	int n;
	cin >> n;
	Init(n);
	int m;
	cin >> m;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		Link(x, y);
		cout << CountCritical() << "\n";
	}
}
 
signed main(){
	process();
}*/

Compilation message

rings.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:133:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    for(int i = 0; (i + 1) < edges.size(); i++){
      |                   ~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47228 KB Output is correct
2 Correct 36 ms 48084 KB Output is correct
3 Correct 30 ms 48360 KB Output is correct
4 Correct 25 ms 47460 KB Output is correct
5 Correct 25 ms 47676 KB Output is correct
6 Correct 28 ms 48104 KB Output is correct
7 Correct 23 ms 47956 KB Output is correct
8 Correct 32 ms 47780 KB Output is correct
9 Correct 27 ms 48292 KB Output is correct
10 Correct 28 ms 48340 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1301 ms 98188 KB Output is correct
2 Correct 3806 ms 200720 KB Output is correct
3 Execution timed out 4032 ms 228996 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47228 KB Output is correct
2 Correct 36 ms 48084 KB Output is correct
3 Correct 30 ms 48360 KB Output is correct
4 Correct 25 ms 47460 KB Output is correct
5 Correct 25 ms 47676 KB Output is correct
6 Correct 28 ms 48104 KB Output is correct
7 Correct 23 ms 47956 KB Output is correct
8 Correct 32 ms 47780 KB Output is correct
9 Correct 27 ms 48292 KB Output is correct
10 Correct 28 ms 48340 KB Output is correct
11 Correct 30 ms 48340 KB Output is correct
12 Correct 43 ms 49608 KB Output is correct
13 Correct 39 ms 49248 KB Output is correct
14 Correct 30 ms 48888 KB Output is correct
15 Correct 30 ms 49912 KB Output is correct
16 Correct 32 ms 48548 KB Output is correct
17 Correct 33 ms 49228 KB Output is correct
18 Correct 40 ms 50528 KB Output is correct
19 Correct 39 ms 48596 KB Output is correct
20 Correct 46 ms 49268 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47228 KB Output is correct
2 Correct 36 ms 48084 KB Output is correct
3 Correct 30 ms 48360 KB Output is correct
4 Correct 25 ms 47460 KB Output is correct
5 Correct 25 ms 47676 KB Output is correct
6 Correct 28 ms 48104 KB Output is correct
7 Correct 23 ms 47956 KB Output is correct
8 Correct 32 ms 47780 KB Output is correct
9 Correct 27 ms 48292 KB Output is correct
10 Correct 28 ms 48340 KB Output is correct
11 Correct 30 ms 48340 KB Output is correct
12 Correct 43 ms 49608 KB Output is correct
13 Correct 39 ms 49248 KB Output is correct
14 Correct 30 ms 48888 KB Output is correct
15 Correct 30 ms 49912 KB Output is correct
16 Correct 32 ms 48548 KB Output is correct
17 Correct 33 ms 49228 KB Output is correct
18 Correct 40 ms 50528 KB Output is correct
19 Correct 39 ms 48596 KB Output is correct
20 Correct 46 ms 49268 KB Output is correct
21 Correct 56 ms 50376 KB Output is correct
22 Correct 82 ms 52128 KB Output is correct
23 Correct 105 ms 53504 KB Output is correct
24 Correct 163 ms 61044 KB Output is correct
25 Correct 45 ms 58332 KB Output is correct
26 Correct 124 ms 63020 KB Output is correct
27 Correct 152 ms 57684 KB Output is correct
28 Correct 138 ms 64468 KB Output is correct
29 Correct 87 ms 61824 KB Output is correct
30 Correct 227 ms 60808 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47228 KB Output is correct
2 Correct 36 ms 48084 KB Output is correct
3 Correct 30 ms 48360 KB Output is correct
4 Correct 25 ms 47460 KB Output is correct
5 Correct 25 ms 47676 KB Output is correct
6 Correct 28 ms 48104 KB Output is correct
7 Correct 23 ms 47956 KB Output is correct
8 Correct 32 ms 47780 KB Output is correct
9 Correct 27 ms 48292 KB Output is correct
10 Correct 28 ms 48340 KB Output is correct
11 Correct 1301 ms 98188 KB Output is correct
12 Correct 3806 ms 200720 KB Output is correct
13 Execution timed out 4032 ms 228996 KB Time limit exceeded
14 Halted 0 ms 0 KB -