oj.uz

답안 #350952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350952 2021-01-19T10:11:59 Z tengiz05 낙하산 고리들 (IOI12_rings) C++17
0 / 100
 4000 ms 180836 KB 
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int Ni = 1e6+5;
vector<int> edges[Ni];
int n, ans;
vector<int> p;
vector<int> sz;
int par(int u){
	if(p[u] == u)return u;
	return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
	return par(u) == par(v);
}
void merge(int u,int v){
	u=par(u);v=par(v);
	if(u == v)return;
	p[v] = u;
	sz[u] += sz[v];
	return;
}
int size_of_node(int u){
	return sz[par(u)];
}
int have_this_number_of_edges[5];
void Init(int N_) {
	n = N_;
	ans = n;
	p.assign(n,0);
	sz.assign(n,0);
	for(int i=0;i<n;i++)p[i] = i;
	have_this_number_of_edges[0] = n;
}
int number_of_cycles;
void del(int u){
	have_this_number_of_edges[min(4,(int)edges[u].size())]--;
}void add(int u){
	have_this_number_of_edges[min(4,(int)edges[u].size())]++;	
}
void Link(int u, int v){
	del(u);del(v);
	edges[u].pb(v);
	edges[v].pb(u);
	add(u);add(v);
	if(IsSame(u, v)){
		number_of_cycles++;
	}else {
		merge(u,v);
	}return;
}

int please_dont_go_there;
bool is_it_normal;
bool used[Ni];

void dfs(int u, int p){
	used[u] = true;
	int cnt= 0 ;
	for(auto v : edges[u]){
		if(v != please_dont_go_there)cnt++;
		if(v == p || v == please_dont_go_there)continue;
		if(used[v])is_it_normal = false;
		else dfs(v,u);
	}if(cnt>2)is_it_normal = false;
}

bool CheckItPlease(int to_delete){
	please_dont_go_there = to_delete;
	for(int j=0;j<n;j++)used[j] = false;
	used[please_dont_go_there] = true;
	is_it_normal = true;
	for(int j=0;j<n;j++){
		if(!used[j])dfs(j,j);
	}return is_it_normal;
}

bool is_it_in_cycle[Ni];
int parent[Ni];
void PleaseFindCycles(int u, int p){
	parent[u] = p;
	used[u] = true;
	for(auto v : edges[u]){
		if(v == p)continue;
		if(used[v]){
			int x = u;
			while(x != v){
				cout << x << ' ';
				is_it_in_cycle[x]=1;
				x=parent[x];
			}is_it_in_cycle[x]=1;
		}else {
			PleaseFindCycles(v,u);
		}
	}
}
int CountCritical(){
	if(have_this_number_of_edges[4] > 1)return 0;
	if(!number_of_cycles && have_this_number_of_edges[3]+have_this_number_of_edges[4]==0)return n;
	ans = 0;
	for(int i=0;i<n;i++){
		used[i] = is_it_in_cycle[i] = false;
	}	if(have_this_number_of_edges[4] == 1){
		int we_need_it;
		for(int i=0;i<n;i++){
			if(edges[i].size() >= 4){
				we_need_it = i;break;
			}
		}
		ans += CheckItPlease(we_need_it);
	}else if(have_this_number_of_edges[3] > 0){
		int we_need_it;
		for(int i=0;i<n;i++){
			if(edges[i].size() == 3){
				we_need_it = i;break;
			}
		}
		ans += CheckItPlease(we_need_it);
		for(auto v : edges[we_need_it])ans += CheckItPlease(v);	
	}else if(have_this_number_of_edges[2] > 0){
		for(int i=0;i<n;i++){
			if(!used[i]){
				PleaseFindCycles(i,i);
			}
		}

		for(int i=0;i<n;i++){
			if(is_it_in_cycle[i]){
				return size_of_node(i);
			}
		}return n;
	}else assert(false);
	return ans;
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:115:7: warning: 'we_need_it' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |   int we_need_it;
      |       ^~~~~~~~~~
rings.cpp:113:23: warning: 'we_need_it' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |   ans += CheckItPlease(we_need_it);
      |          ~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Execution timed out 4072 ms 109704 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 489 ms 44188 KB Output is correct
2 Correct 1154 ms 57020 KB Output is correct
3 Correct 1168 ms 58976 KB Output is correct
4 Execution timed out 4081 ms 180836 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Execution timed out 4072 ms 109704 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Execution timed out 4072 ms 109704 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 18 ms 24044 KB Output is correct
3 Correct 17 ms 24044 KB Output is correct
4 Execution timed out 4072 ms 109704 KB Time limit exceeded
5 Halted 0 ms 0 KB -