oj.uz

Submission #575879

# Submission time Handle Problem Language Result Execution time Memory
575879 2022-06-11T12:56:18 Z arneves Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 44076 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;

const int MX=1e6+5;
int n;
vector<int> adj[MX];
int visitados[MX];
int grau[MX];
vector<int> cand;
vector<int> grau3;
vector<int> grau4;

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

void Link(int A, int B){
	adj[A].push_back(B);
	adj[B].push_back(A);
	
	if(adj[A].size()==3){
		grau3.push_back(A);
		for(auto u: adj[A]) cand.push_back(u);
	}
	if(adj[B].size()==3){
		grau3.push_back(B);
		for(auto u: adj[B]) cand.push_back(u);
	}
	if(adj[A].size()==4){
		grau4.push_back(A);
	}
	if(adj[B].size()==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;
	}
	
	int ans=0;
	for(int i=0; i<n; i++) if(f(i)) ans++;//, cout<<i<<" ";
	
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24012 KB Output is correct
3 Correct 14 ms 23964 KB Output is correct
4 Correct 22 ms 23764 KB Output is correct
5 Correct 344 ms 23960 KB Output is correct
6 Correct 1228 ms 24120 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 67 ms 23996 KB Output is correct
9 Correct 15 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 44076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24012 KB Output is correct
3 Correct 14 ms 23964 KB Output is correct
4 Correct 22 ms 23764 KB Output is correct
5 Correct 344 ms 23960 KB Output is correct
6 Correct 1228 ms 24120 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 67 ms 23996 KB Output is correct
9 Correct 15 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Execution timed out 4086 ms 23912 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24012 KB Output is correct
3 Correct 14 ms 23964 KB Output is correct
4 Correct 22 ms 23764 KB Output is correct
5 Correct 344 ms 23960 KB Output is correct
6 Correct 1228 ms 24120 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 67 ms 23996 KB Output is correct
9 Correct 15 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Execution timed out 4086 ms 23912 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 17 ms 24012 KB Output is correct
3 Correct 14 ms 23964 KB Output is correct
4 Correct 22 ms 23764 KB Output is correct
5 Correct 344 ms 23960 KB Output is correct
6 Correct 1228 ms 24120 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 67 ms 23996 KB Output is correct
9 Correct 15 ms 24020 KB Output is correct
10 Correct 15 ms 24020 KB Output is correct
11 Execution timed out 4067 ms 44076 KB Time limit exceeded
12 Halted 0 ms 0 KB -