oj.uz

Submission #575889

# Submission time Handle Problem Language Result Execution time Memory
575889 2022-06-11T13:46:31 Z arneves Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 94552 KB 
/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
	       .      .           .      .           .      .    	
	       _\/  \/_           _\/  \/_           _\/  \/_    	
	        _\/\/_             _\/\/_             _\/\/_     	
	    _\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
	     / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
	        _/\/\_             _/\/\_             _/\/\_     	
	        /\  /\             /\  /\             /\  /\     	
	       '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
 
using namespace std;
typedef long long ll;

class DSU //with range compression and union by subtree size
{
	public:
	ll N;
	vector<ll> p,siz;
	
	DSU(ll n)
	{
		N=n; for(int i=0; i<N; i++){p.push_back(i); siz.push_back(1);}
	}
	
	ll find(ll x)
	{
		if(p[x]==x) {return x;}
		ll ans=find(p[x]);
		p[x]=ans; 
		return ans;
	}
	
	void unionn(ll a, ll b)
	{
		a=find(a); b=find(b);
		if(a==b) {return;}
		if(siz[a]>siz[b]) {swap(a,b);}
		p[a]=b; siz[b]+=siz[a];
	}
};

const int MX=1e6+5;
int n;
vector<int> adj[MX];
int visitados[MX];
int grau[MX];
int ciclos=0;
vector<int> gajos_no_ciclo;
vector<int> cand;
vector<int> grau3;
vector<int> grau4;
DSU dsu(MX);

void Init(int N){
	n=N;
	for(int i=0; i<n; i++) grau[i]=0;
}

int dfs2(int s, int p, int t){
	int ans=0;
	for(auto u: adj[s]){
		if(u!=p){
			if(u==t){
				ans++;
			}else{
				ans+=dfs2(u,s,t);
			}
		}
	}
	if(ans){
		gajos_no_ciclo.push_back(s);
		return 1;
	}else{
		return 0;
	}
}

void Link(int A, int B){
	adj[A].push_back(B);
	adj[B].push_back(A);
	grau[A]++;
	grau[B]++;
	if(dsu.find(A)==dsu.find(B)){
		if(ciclos==0){
			dfs2(A,-1,B);
			gajos_no_ciclo.push_back(B);
		}
		ciclos++;
	}
	
	dsu.unionn(A,B);
	
	if(grau[A]==3){
		grau3.push_back(A);
		for(auto u: adj[A]) cand.push_back(u);
	}
	if(grau[B]==3){
		grau3.push_back(B);
		for(auto u: adj[B]) cand.push_back(u);
	}
	if(grau[A]==4){
		grau4.push_back(A);
	}
	if(grau[B]==4){
		grau4.push_back(B);
	}
}

int dfs(int s, int p, int pro){
	visitados[s]=1;
	int ans=0;
	for(auto u: adj[s]){
		if(u!=p && u!=s && u!=pro){
			if(visitados[u]) return 1;
			else ans+=dfs(u,s,pro);
		}
	}
	return ans>0;
}

int f(int u){
	for(int i=0; i<n; i++){
		if(i==u) continue;
		vector<int> v;
		for(auto y: adj[i]) if(y!=u) v.push_back(y);
		if(v.size()>2) return 0;
	}
	for(int i=0; i<n; i++) visitados[i]=0;
	for(int i=0; i<n; i++){
		if(i!=u && !visitados[i]){
			if(dfs(i,-1,u)){
				return 0;
			}
		}
	}
	return 1;
}

int CountCritical(){
	if(grau4.size()>=2) return 0;
	if(grau4.size()==1) return f(grau4[0]);
	if(grau3.size()>=5) return 0;
	if(grau3.size()>0){
		int ans=0;
		set<int> s;
		for(auto u: cand) s.insert(u);
		for(auto u: grau3) s.insert(u); 
		for(auto u: s) if(f(u)) ans++;
		return ans;
	}
	if(ciclos>=2){
		return 0;
	}
	if(ciclos==1){
		return gajos_no_ciclo.size();
	}
	
	/*int ans=0;
	for(int i=0; i<n; i++) if(f(i)) ans++;//, cout<<i<<" ";*/
	
	return n;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39672 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 34 ms 39804 KB Output is correct
4 Correct 31 ms 39720 KB Output is correct
5 Correct 29 ms 39772 KB Output is correct
6 Correct 31 ms 39928 KB Output is correct
7 Correct 29 ms 39660 KB Output is correct
8 Correct 31 ms 39712 KB Output is correct
9 Correct 32 ms 39892 KB Output is correct
10 Correct 31 ms 39848 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 57920 KB Output is correct
2 Correct 1054 ms 70928 KB Output is correct
3 Correct 912 ms 76224 KB Output is correct
4 Correct 988 ms 74652 KB Output is correct
5 Correct 991 ms 75552 KB Output is correct
6 Correct 1076 ms 94552 KB Output is correct
7 Correct 882 ms 75812 KB Output is correct
8 Correct 1659 ms 76568 KB Output is correct
9 Correct 1674 ms 79040 KB Output is correct
10 Correct 671 ms 72976 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39672 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 34 ms 39804 KB Output is correct
4 Correct 31 ms 39720 KB Output is correct
5 Correct 29 ms 39772 KB Output is correct
6 Correct 31 ms 39928 KB Output is correct
7 Correct 29 ms 39660 KB Output is correct
8 Correct 31 ms 39712 KB Output is correct
9 Correct 32 ms 39892 KB Output is correct
10 Correct 31 ms 39848 KB Output is correct
11 Correct 57 ms 39824 KB Output is correct
12 Correct 45 ms 40112 KB Output is correct
13 Correct 112 ms 39992 KB Output is correct
14 Correct 60 ms 39932 KB Output is correct
15 Correct 57 ms 40008 KB Output is correct
16 Correct 36 ms 39920 KB Output is correct
17 Correct 32 ms 40016 KB Output is correct
18 Correct 33 ms 40096 KB Output is correct
19 Correct 31 ms 40032 KB Output is correct
20 Correct 113 ms 40012 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39672 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 34 ms 39804 KB Output is correct
4 Correct 31 ms 39720 KB Output is correct
5 Correct 29 ms 39772 KB Output is correct
6 Correct 31 ms 39928 KB Output is correct
7 Correct 29 ms 39660 KB Output is correct
8 Correct 31 ms 39712 KB Output is correct
9 Correct 32 ms 39892 KB Output is correct
10 Correct 31 ms 39848 KB Output is correct
11 Correct 57 ms 39824 KB Output is correct
12 Correct 45 ms 40112 KB Output is correct
13 Correct 112 ms 39992 KB Output is correct
14 Correct 60 ms 39932 KB Output is correct
15 Correct 57 ms 40008 KB Output is correct
16 Correct 36 ms 39920 KB Output is correct
17 Correct 32 ms 40016 KB Output is correct
18 Correct 33 ms 40096 KB Output is correct
19 Correct 31 ms 40032 KB Output is correct
20 Correct 113 ms 40012 KB Output is correct
21 Correct 43 ms 40772 KB Output is correct
22 Correct 52 ms 41400 KB Output is correct
23 Correct 63 ms 42028 KB Output is correct
24 Execution timed out 4082 ms 40784 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39672 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 34 ms 39804 KB Output is correct
4 Correct 31 ms 39720 KB Output is correct
5 Correct 29 ms 39772 KB Output is correct
6 Correct 31 ms 39928 KB Output is correct
7 Correct 29 ms 39660 KB Output is correct
8 Correct 31 ms 39712 KB Output is correct
9 Correct 32 ms 39892 KB Output is correct
10 Correct 31 ms 39848 KB Output is correct
11 Correct 382 ms 57920 KB Output is correct
12 Correct 1054 ms 70928 KB Output is correct
13 Correct 912 ms 76224 KB Output is correct
14 Correct 988 ms 74652 KB Output is correct
15 Correct 991 ms 75552 KB Output is correct
16 Correct 1076 ms 94552 KB Output is correct
17 Correct 882 ms 75812 KB Output is correct
18 Correct 1659 ms 76568 KB Output is correct
19 Correct 1674 ms 79040 KB Output is correct
20 Correct 671 ms 72976 KB Output is correct
21 Correct 57 ms 39824 KB Output is correct
22 Correct 45 ms 40112 KB Output is correct
23 Correct 112 ms 39992 KB Output is correct
24 Correct 60 ms 39932 KB Output is correct
25 Correct 57 ms 40008 KB Output is correct
26 Correct 36 ms 39920 KB Output is correct
27 Correct 32 ms 40016 KB Output is correct
28 Correct 33 ms 40096 KB Output is correct
29 Correct 31 ms 40032 KB Output is correct
30 Correct 113 ms 40012 KB Output is correct
31 Correct 43 ms 40772 KB Output is correct
32 Correct 52 ms 41400 KB Output is correct
33 Correct 63 ms 42028 KB Output is correct
34 Execution timed out 4082 ms 40784 KB Time limit exceeded
35 Halted 0 ms 0 KB -