oj.uz

Submission #575892

# Submission time Handle Problem Language Result Execution time Memory
575892 2022-06-11T13:53:46 Z arneves Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 94712 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);

int last=-1;
int ready=0;

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);
	}
	ready=0;
}

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(last==0 || ready==1) return last;
	ready=1;
	if(grau4.size()>=2) return last=0;
	if(grau4.size()==1) return last=f(grau4[0]);
	if(grau3.size()>=5) return last=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++;
		last=ans;
		return ans;
	}
	if(ciclos>=2){
		return last=0;
	}
	if(ciclos==1){
		return last=gajos_no_ciclo.size();
	}
	
	/*int ans=0;
	for(int i=0; i<n; i++) if(f(i)) ans++;//, cout<<i<<" ";*/
	last=n;
	return n;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39592 KB Output is correct
2 Correct 30 ms 39812 KB Output is correct
3 Correct 30 ms 39852 KB Output is correct
4 Correct 29 ms 39624 KB Output is correct
5 Correct 29 ms 39748 KB Output is correct
6 Correct 32 ms 39924 KB Output is correct
7 Correct 28 ms 39720 KB Output is correct
8 Correct 29 ms 39708 KB Output is correct
9 Correct 30 ms 39904 KB Output is correct
10 Correct 33 ms 39860 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 57892 KB Output is correct
2 Correct 1067 ms 71220 KB Output is correct
3 Correct 939 ms 76108 KB Output is correct
4 Correct 991 ms 74800 KB Output is correct
5 Correct 1006 ms 75612 KB Output is correct
6 Correct 1083 ms 94712 KB Output is correct
7 Correct 877 ms 75912 KB Output is correct
8 Correct 1687 ms 76352 KB Output is correct
9 Correct 1722 ms 79044 KB Output is correct
10 Correct 677 ms 73036 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39592 KB Output is correct
2 Correct 30 ms 39812 KB Output is correct
3 Correct 30 ms 39852 KB Output is correct
4 Correct 29 ms 39624 KB Output is correct
5 Correct 29 ms 39748 KB Output is correct
6 Correct 32 ms 39924 KB Output is correct
7 Correct 28 ms 39720 KB Output is correct
8 Correct 29 ms 39708 KB Output is correct
9 Correct 30 ms 39904 KB Output is correct
10 Correct 33 ms 39860 KB Output is correct
11 Correct 60 ms 39832 KB Output is correct
12 Correct 48 ms 40060 KB Output is correct
13 Correct 98 ms 39964 KB Output is correct
14 Correct 52 ms 39944 KB Output is correct
15 Correct 53 ms 39956 KB Output is correct
16 Correct 35 ms 39960 KB Output is correct
17 Correct 32 ms 40000 KB Output is correct
18 Correct 32 ms 40140 KB Output is correct
19 Correct 35 ms 39968 KB Output is correct
20 Correct 108 ms 40016 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39592 KB Output is correct
2 Correct 30 ms 39812 KB Output is correct
3 Correct 30 ms 39852 KB Output is correct
4 Correct 29 ms 39624 KB Output is correct
5 Correct 29 ms 39748 KB Output is correct
6 Correct 32 ms 39924 KB Output is correct
7 Correct 28 ms 39720 KB Output is correct
8 Correct 29 ms 39708 KB Output is correct
9 Correct 30 ms 39904 KB Output is correct
10 Correct 33 ms 39860 KB Output is correct
11 Correct 60 ms 39832 KB Output is correct
12 Correct 48 ms 40060 KB Output is correct
13 Correct 98 ms 39964 KB Output is correct
14 Correct 52 ms 39944 KB Output is correct
15 Correct 53 ms 39956 KB Output is correct
16 Correct 35 ms 39960 KB Output is correct
17 Correct 32 ms 40000 KB Output is correct
18 Correct 32 ms 40140 KB Output is correct
19 Correct 35 ms 39968 KB Output is correct
20 Correct 108 ms 40016 KB Output is correct
21 Correct 43 ms 40788 KB Output is correct
22 Correct 54 ms 41428 KB Output is correct
23 Correct 62 ms 42036 KB Output is correct
24 Execution timed out 4056 ms 41244 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39592 KB Output is correct
2 Correct 30 ms 39812 KB Output is correct
3 Correct 30 ms 39852 KB Output is correct
4 Correct 29 ms 39624 KB Output is correct
5 Correct 29 ms 39748 KB Output is correct
6 Correct 32 ms 39924 KB Output is correct
7 Correct 28 ms 39720 KB Output is correct
8 Correct 29 ms 39708 KB Output is correct
9 Correct 30 ms 39904 KB Output is correct
10 Correct 33 ms 39860 KB Output is correct
11 Correct 379 ms 57892 KB Output is correct
12 Correct 1067 ms 71220 KB Output is correct
13 Correct 939 ms 76108 KB Output is correct
14 Correct 991 ms 74800 KB Output is correct
15 Correct 1006 ms 75612 KB Output is correct
16 Correct 1083 ms 94712 KB Output is correct
17 Correct 877 ms 75912 KB Output is correct
18 Correct 1687 ms 76352 KB Output is correct
19 Correct 1722 ms 79044 KB Output is correct
20 Correct 677 ms 73036 KB Output is correct
21 Correct 60 ms 39832 KB Output is correct
22 Correct 48 ms 40060 KB Output is correct
23 Correct 98 ms 39964 KB Output is correct
24 Correct 52 ms 39944 KB Output is correct
25 Correct 53 ms 39956 KB Output is correct
26 Correct 35 ms 39960 KB Output is correct
27 Correct 32 ms 40000 KB Output is correct
28 Correct 32 ms 40140 KB Output is correct
29 Correct 35 ms 39968 KB Output is correct
30 Correct 108 ms 40016 KB Output is correct
31 Correct 43 ms 40788 KB Output is correct
32 Correct 54 ms 41428 KB Output is correct
33 Correct 62 ms 42036 KB Output is correct
34 Execution timed out 4056 ms 41244 KB Time limit exceeded
35 Halted 0 ms 0 KB -