oj.uz

Submission #575872

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

void Init(int N) {
	n=N;
}

void Link(int A, int B) {
	adj[A].push_back(B);
	adj[B].push_back(A);
}

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() {
	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 873 ms 24012 KB Output is correct
3 Correct 688 ms 24140 KB Output is correct
4 Correct 24 ms 23764 KB Output is correct
5 Correct 342 ms 23976 KB Output is correct
6 Correct 1229 ms 24136 KB Output is correct
7 Correct 124 ms 23764 KB Output is correct
8 Correct 65 ms 23996 KB Output is correct
9 Correct 552 ms 24072 KB Output is correct
10 Correct 606 ms 24020 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 48972 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 873 ms 24012 KB Output is correct
3 Correct 688 ms 24140 KB Output is correct
4 Correct 24 ms 23764 KB Output is correct
5 Correct 342 ms 23976 KB Output is correct
6 Correct 1229 ms 24136 KB Output is correct
7 Correct 124 ms 23764 KB Output is correct
8 Correct 65 ms 23996 KB Output is correct
9 Correct 552 ms 24072 KB Output is correct
10 Correct 606 ms 24020 KB Output is correct
11 Execution timed out 4034 ms 24028 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 873 ms 24012 KB Output is correct
3 Correct 688 ms 24140 KB Output is correct
4 Correct 24 ms 23764 KB Output is correct
5 Correct 342 ms 23976 KB Output is correct
6 Correct 1229 ms 24136 KB Output is correct
7 Correct 124 ms 23764 KB Output is correct
8 Correct 65 ms 23996 KB Output is correct
9 Correct 552 ms 24072 KB Output is correct
10 Correct 606 ms 24020 KB Output is correct
11 Execution timed out 4034 ms 24028 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 873 ms 24012 KB Output is correct
3 Correct 688 ms 24140 KB Output is correct
4 Correct 24 ms 23764 KB Output is correct
5 Correct 342 ms 23976 KB Output is correct
6 Correct 1229 ms 24136 KB Output is correct
7 Correct 124 ms 23764 KB Output is correct
8 Correct 65 ms 23996 KB Output is correct
9 Correct 552 ms 24072 KB Output is correct
10 Correct 606 ms 24020 KB Output is correct
11 Execution timed out 4054 ms 48972 KB Time limit exceeded
12 Halted 0 ms 0 KB -