oj.uz

Submission #575888

# Submission time Handle Problem Language Result Execution time Memory
575888 2022-06-11T13:42:00 Z arneves Parachute rings (IOI12_rings) C++17
37 / 100
 3039 ms 94592 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()>=3) 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 39584 KB Output is correct
2 Correct 30 ms 39788 KB Output is correct
3 Correct 31 ms 39848 KB Output is correct
4 Correct 28 ms 39632 KB Output is correct
5 Correct 30 ms 39848 KB Output is correct
6 Correct 31 ms 39976 KB Output is correct
7 Correct 35 ms 39720 KB Output is correct
8 Correct 32 ms 39720 KB Output is correct
9 Correct 32 ms 39832 KB Output is correct
10 Correct 32 ms 39792 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 57908 KB Output is correct
2 Correct 1062 ms 71072 KB Output is correct
3 Correct 915 ms 76128 KB Output is correct
4 Correct 1010 ms 74724 KB Output is correct
5 Correct 984 ms 75664 KB Output is correct
6 Correct 1086 ms 94592 KB Output is correct
7 Correct 880 ms 75752 KB Output is correct
8 Correct 2533 ms 76416 KB Output is correct
9 Correct 3039 ms 79140 KB Output is correct
10 Correct 681 ms 72996 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39584 KB Output is correct
2 Correct 30 ms 39788 KB Output is correct
3 Correct 31 ms 39848 KB Output is correct
4 Correct 28 ms 39632 KB Output is correct
5 Correct 30 ms 39848 KB Output is correct
6 Correct 31 ms 39976 KB Output is correct
7 Correct 35 ms 39720 KB Output is correct
8 Correct 32 ms 39720 KB Output is correct
9 Correct 32 ms 39832 KB Output is correct
10 Correct 32 ms 39792 KB Output is correct
11 Incorrect 55 ms 39844 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39584 KB Output is correct
2 Correct 30 ms 39788 KB Output is correct
3 Correct 31 ms 39848 KB Output is correct
4 Correct 28 ms 39632 KB Output is correct
5 Correct 30 ms 39848 KB Output is correct
6 Correct 31 ms 39976 KB Output is correct
7 Correct 35 ms 39720 KB Output is correct
8 Correct 32 ms 39720 KB Output is correct
9 Correct 32 ms 39832 KB Output is correct
10 Correct 32 ms 39792 KB Output is correct
11 Incorrect 55 ms 39844 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39584 KB Output is correct
2 Correct 30 ms 39788 KB Output is correct
3 Correct 31 ms 39848 KB Output is correct
4 Correct 28 ms 39632 KB Output is correct
5 Correct 30 ms 39848 KB Output is correct
6 Correct 31 ms 39976 KB Output is correct
7 Correct 35 ms 39720 KB Output is correct
8 Correct 32 ms 39720 KB Output is correct
9 Correct 32 ms 39832 KB Output is correct
10 Correct 32 ms 39792 KB Output is correct
11 Correct 381 ms 57908 KB Output is correct
12 Correct 1062 ms 71072 KB Output is correct
13 Correct 915 ms 76128 KB Output is correct
14 Correct 1010 ms 74724 KB Output is correct
15 Correct 984 ms 75664 KB Output is correct
16 Correct 1086 ms 94592 KB Output is correct
17 Correct 880 ms 75752 KB Output is correct
18 Correct 2533 ms 76416 KB Output is correct
19 Correct 3039 ms 79140 KB Output is correct
20 Correct 681 ms 72996 KB Output is correct
21 Incorrect 55 ms 39844 KB Output isn't correct
22 Halted 0 ms 0 KB -