oj.uz

Submission #575887

# Submission time Handle Problem Language Result Execution time Memory
575887 2022-06-11T13:38:58 Z arneves Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 94640 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++) visitados[i]=0;
	for(int i=0; i<n; i++){
		if(i!=u && !visitados[i]){
			if(dfs(i,-1,u)){
				return 0;
			}
		}
	}
	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;
	}
	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 30 ms 39652 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 31 ms 39808 KB Output is correct
4 Correct 29 ms 39656 KB Output is correct
5 Correct 31 ms 39864 KB Output is correct
6 Correct 32 ms 40012 KB Output is correct
7 Correct 29 ms 39712 KB Output is correct
8 Correct 32 ms 39732 KB Output is correct
9 Correct 32 ms 39844 KB Output is correct
10 Correct 33 ms 39804 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 57948 KB Output is correct
2 Correct 1088 ms 71080 KB Output is correct
3 Correct 920 ms 76336 KB Output is correct
4 Correct 1002 ms 74744 KB Output is correct
5 Correct 1002 ms 75564 KB Output is correct
6 Correct 1079 ms 94640 KB Output is correct
7 Correct 874 ms 75780 KB Output is correct
8 Correct 2506 ms 76380 KB Output is correct
9 Correct 3039 ms 79076 KB Output is correct
10 Correct 679 ms 73132 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39652 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 31 ms 39808 KB Output is correct
4 Correct 29 ms 39656 KB Output is correct
5 Correct 31 ms 39864 KB Output is correct
6 Correct 32 ms 40012 KB Output is correct
7 Correct 29 ms 39712 KB Output is correct
8 Correct 32 ms 39732 KB Output is correct
9 Correct 32 ms 39844 KB Output is correct
10 Correct 33 ms 39804 KB Output is correct
11 Correct 56 ms 39840 KB Output is correct
12 Correct 45 ms 40056 KB Output is correct
13 Correct 103 ms 40036 KB Output is correct
14 Correct 55 ms 39936 KB Output is correct
15 Correct 56 ms 40052 KB Output is correct
16 Correct 33 ms 39976 KB Output is correct
17 Correct 34 ms 39984 KB Output is correct
18 Correct 37 ms 40184 KB Output is correct
19 Correct 32 ms 39976 KB Output is correct
20 Correct 160 ms 40068 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39652 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 31 ms 39808 KB Output is correct
4 Correct 29 ms 39656 KB Output is correct
5 Correct 31 ms 39864 KB Output is correct
6 Correct 32 ms 40012 KB Output is correct
7 Correct 29 ms 39712 KB Output is correct
8 Correct 32 ms 39732 KB Output is correct
9 Correct 32 ms 39844 KB Output is correct
10 Correct 33 ms 39804 KB Output is correct
11 Correct 56 ms 39840 KB Output is correct
12 Correct 45 ms 40056 KB Output is correct
13 Correct 103 ms 40036 KB Output is correct
14 Correct 55 ms 39936 KB Output is correct
15 Correct 56 ms 40052 KB Output is correct
16 Correct 33 ms 39976 KB Output is correct
17 Correct 34 ms 39984 KB Output is correct
18 Correct 37 ms 40184 KB Output is correct
19 Correct 32 ms 39976 KB Output is correct
20 Correct 160 ms 40068 KB Output is correct
21 Correct 44 ms 40780 KB Output is correct
22 Correct 55 ms 41444 KB Output is correct
23 Correct 58 ms 41920 KB Output is correct
24 Execution timed out 4075 ms 41052 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39652 KB Output is correct
2 Correct 31 ms 39848 KB Output is correct
3 Correct 31 ms 39808 KB Output is correct
4 Correct 29 ms 39656 KB Output is correct
5 Correct 31 ms 39864 KB Output is correct
6 Correct 32 ms 40012 KB Output is correct
7 Correct 29 ms 39712 KB Output is correct
8 Correct 32 ms 39732 KB Output is correct
9 Correct 32 ms 39844 KB Output is correct
10 Correct 33 ms 39804 KB Output is correct
11 Correct 379 ms 57948 KB Output is correct
12 Correct 1088 ms 71080 KB Output is correct
13 Correct 920 ms 76336 KB Output is correct
14 Correct 1002 ms 74744 KB Output is correct
15 Correct 1002 ms 75564 KB Output is correct
16 Correct 1079 ms 94640 KB Output is correct
17 Correct 874 ms 75780 KB Output is correct
18 Correct 2506 ms 76380 KB Output is correct
19 Correct 3039 ms 79076 KB Output is correct
20 Correct 679 ms 73132 KB Output is correct
21 Correct 56 ms 39840 KB Output is correct
22 Correct 45 ms 40056 KB Output is correct
23 Correct 103 ms 40036 KB Output is correct
24 Correct 55 ms 39936 KB Output is correct
25 Correct 56 ms 40052 KB Output is correct
26 Correct 33 ms 39976 KB Output is correct
27 Correct 34 ms 39984 KB Output is correct
28 Correct 37 ms 40184 KB Output is correct
29 Correct 32 ms 39976 KB Output is correct
30 Correct 160 ms 40068 KB Output is correct
31 Correct 44 ms 40780 KB Output is correct
32 Correct 55 ms 41444 KB Output is correct
33 Correct 58 ms 41920 KB Output is correct
34 Execution timed out 4075 ms 41052 KB Time limit exceeded
35 Halted 0 ms 0 KB -