oj.uz

Submission #752017

# Submission time Handle Problem Language Result Execution time Memory
752017 2023-06-02T05:18:49 Z minhcool Parachute rings (IOI12_rings) C++17
52 / 100
 1236 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 = 2e6 + 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][20], mxdeg[20];
 
bool out[N];
 
int sz[N][20], rt[N][20];
 
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);
				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);
				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 44 ms 94216 KB Output is correct
2 Correct 51 ms 95732 KB Output is correct
3 Correct 54 ms 95936 KB Output is correct
4 Correct 46 ms 94296 KB Output is correct
5 Correct 48 ms 94668 KB Output is correct
6 Correct 51 ms 95108 KB Output is correct
7 Correct 47 ms 95564 KB Output is correct
8 Correct 48 ms 94772 KB Output is correct
9 Correct 52 ms 95948 KB Output is correct
10 Correct 50 ms 96020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 145240 KB Output is correct
2 Runtime error 793 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94216 KB Output is correct
2 Correct 51 ms 95732 KB Output is correct
3 Correct 54 ms 95936 KB Output is correct
4 Correct 46 ms 94296 KB Output is correct
5 Correct 48 ms 94668 KB Output is correct
6 Correct 51 ms 95108 KB Output is correct
7 Correct 47 ms 95564 KB Output is correct
8 Correct 48 ms 94772 KB Output is correct
9 Correct 52 ms 95948 KB Output is correct
10 Correct 50 ms 96020 KB Output is correct
11 Correct 50 ms 96024 KB Output is correct
12 Correct 58 ms 97964 KB Output is correct
13 Correct 57 ms 97616 KB Output is correct
14 Correct 51 ms 97212 KB Output is correct
15 Correct 57 ms 99532 KB Output is correct
16 Correct 53 ms 95516 KB Output is correct
17 Correct 68 ms 97600 KB Output is correct
18 Correct 57 ms 100292 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 59 ms 97732 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94216 KB Output is correct
2 Correct 51 ms 95732 KB Output is correct
3 Correct 54 ms 95936 KB Output is correct
4 Correct 46 ms 94296 KB Output is correct
5 Correct 48 ms 94668 KB Output is correct
6 Correct 51 ms 95108 KB Output is correct
7 Correct 47 ms 95564 KB Output is correct
8 Correct 48 ms 94772 KB Output is correct
9 Correct 52 ms 95948 KB Output is correct
10 Correct 50 ms 96020 KB Output is correct
11 Correct 50 ms 96024 KB Output is correct
12 Correct 58 ms 97964 KB Output is correct
13 Correct 57 ms 97616 KB Output is correct
14 Correct 51 ms 97212 KB Output is correct
15 Correct 57 ms 99532 KB Output is correct
16 Correct 53 ms 95516 KB Output is correct
17 Correct 68 ms 97600 KB Output is correct
18 Correct 57 ms 100292 KB Output is correct
19 Correct 54 ms 95588 KB Output is correct
20 Correct 59 ms 97732 KB Output is correct
21 Correct 79 ms 97352 KB Output is correct
22 Correct 101 ms 98984 KB Output is correct
23 Correct 115 ms 100408 KB Output is correct
24 Correct 151 ms 121036 KB Output is correct
25 Correct 75 ms 119372 KB Output is correct
26 Correct 151 ms 123348 KB Output is correct
27 Correct 174 ms 104680 KB Output is correct
28 Correct 1030 ms 123856 KB Output is correct
29 Correct 137 ms 122952 KB Output is correct
30 Correct 263 ms 107836 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94216 KB Output is correct
2 Correct 51 ms 95732 KB Output is correct
3 Correct 54 ms 95936 KB Output is correct
4 Correct 46 ms 94296 KB Output is correct
5 Correct 48 ms 94668 KB Output is correct
6 Correct 51 ms 95108 KB Output is correct
7 Correct 47 ms 95564 KB Output is correct
8 Correct 48 ms 94772 KB Output is correct
9 Correct 52 ms 95948 KB Output is correct
10 Correct 50 ms 96020 KB Output is correct
11 Correct 1236 ms 145240 KB Output is correct
12 Runtime error 793 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -