oj.uz

Submission #752022

# Submission time Handle Problem Language Result Execution time Memory
752022 2023-06-02T05:29:47 Z minhcool Parachute rings (IOI12_rings) C++17
52 / 100
 4000 ms 262144 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][10], mxdeg[10];
 
bool out[N];
 
int sz[N][10], rt[N][10];
 
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;
			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 22 ms 47316 KB Output is correct
2 Correct 26 ms 48148 KB Output is correct
3 Correct 27 ms 48440 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 30 ms 47712 KB Output is correct
6 Correct 27 ms 48104 KB Output is correct
7 Correct 22 ms 47956 KB Output is correct
8 Correct 26 ms 47768 KB Output is correct
9 Correct 29 ms 48400 KB Output is correct
10 Correct 31 ms 48388 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 98324 KB Output is correct
2 Correct 3896 ms 230132 KB Output is correct
3 Execution timed out 4065 ms 262144 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 48148 KB Output is correct
3 Correct 27 ms 48440 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 30 ms 47712 KB Output is correct
6 Correct 27 ms 48104 KB Output is correct
7 Correct 22 ms 47956 KB Output is correct
8 Correct 26 ms 47768 KB Output is correct
9 Correct 29 ms 48400 KB Output is correct
10 Correct 31 ms 48388 KB Output is correct
11 Correct 34 ms 48412 KB Output is correct
12 Correct 36 ms 49744 KB Output is correct
13 Correct 39 ms 49392 KB Output is correct
14 Correct 31 ms 49044 KB Output is correct
15 Correct 31 ms 50260 KB Output is correct
16 Correct 33 ms 48544 KB Output is correct
17 Correct 47 ms 49576 KB Output is correct
18 Correct 36 ms 50944 KB Output is correct
19 Correct 35 ms 48652 KB Output is correct
20 Correct 37 ms 49484 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 48148 KB Output is correct
3 Correct 27 ms 48440 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 30 ms 47712 KB Output is correct
6 Correct 27 ms 48104 KB Output is correct
7 Correct 22 ms 47956 KB Output is correct
8 Correct 26 ms 47768 KB Output is correct
9 Correct 29 ms 48400 KB Output is correct
10 Correct 31 ms 48388 KB Output is correct
11 Correct 34 ms 48412 KB Output is correct
12 Correct 36 ms 49744 KB Output is correct
13 Correct 39 ms 49392 KB Output is correct
14 Correct 31 ms 49044 KB Output is correct
15 Correct 31 ms 50260 KB Output is correct
16 Correct 33 ms 48544 KB Output is correct
17 Correct 47 ms 49576 KB Output is correct
18 Correct 36 ms 50944 KB Output is correct
19 Correct 35 ms 48652 KB Output is correct
20 Correct 37 ms 49484 KB Output is correct
21 Correct 62 ms 50376 KB Output is correct
22 Correct 83 ms 52128 KB Output is correct
23 Correct 116 ms 53400 KB Output is correct
24 Correct 148 ms 63324 KB Output is correct
25 Correct 50 ms 60748 KB Output is correct
26 Correct 133 ms 65148 KB Output is correct
27 Correct 153 ms 57808 KB Output is correct
28 Correct 1020 ms 66584 KB Output is correct
29 Correct 99 ms 64124 KB Output is correct
30 Correct 247 ms 60844 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 48148 KB Output is correct
3 Correct 27 ms 48440 KB Output is correct
4 Correct 25 ms 47324 KB Output is correct
5 Correct 30 ms 47712 KB Output is correct
6 Correct 27 ms 48104 KB Output is correct
7 Correct 22 ms 47956 KB Output is correct
8 Correct 26 ms 47768 KB Output is correct
9 Correct 29 ms 48400 KB Output is correct
10 Correct 31 ms 48388 KB Output is correct
11 Correct 1327 ms 98324 KB Output is correct
12 Correct 3896 ms 230132 KB Output is correct
13 Execution timed out 4065 ms 262144 KB Time limit exceeded
14 Halted 0 ms 0 KB -