oj.uz

Submission #286698

# Submission time Handle Problem Language Result Execution time Memory
286698 2020-08-30T18:23:12 Z amiratou Parachute rings (IOI12_rings) C++14
38 / 100
 4000 ms 120656 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;

int N,degree[MX],id[MX],idx,t=1;
vector<int> vec[MX];
multiset<int,greater<int> > comp[MX];
int vis[MX];

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

void Link(int A, int B) {
	vec[A].pb(B),vec[B].pb(A);
	degree[A]++,degree[B]++;
}
void dfs(int node,int k=0){
	vis[node]=t;
	if(!k){
		id[node]=idx;
		comp[idx].insert(degree[node]);
	}
	for(auto it:vec[node])
		if(vis[it]!=t)dfs(it,k);
}
int gimme(int node){
	vis[node]=t;
	int h=0;
	for(auto it:vec[node])
		if(vis[it]!=t)dfs(it,1),h++;
	return h;
}

int CountCritical() {
	idx=0;
	for (int i = 0; i < N; ++i)
		vis[i]=0,comp[i].clear();
	for (int i = 0; i < N; ++i)
		if(vis[i]!=t)dfs(i),idx++;
	set<int> good;
	for (int i = 0; i < idx; ++i)
	{
		if(sz(comp[i])==1)good.insert(i);
		else if((*comp[i].begin())<=2 && comp[i].find(1)!=comp[i].end()){
			comp[i].erase(comp[i].find(1));
			bool f=0;
			if(comp[i].find(1)!=comp[i].end())f=1;
			comp[i].insert(1);
			if(f)good.insert(i);
		}
	}
	//cerr<<idx<<","<<sz(good)<<"\n";
	int ans=0;
	for (int i = 0; i < N; ++i)
	{
		bool g=0;
		if(good.find(id[i])!=good.end())good.erase(id[i]),g=1;
		if(sz(good)==(idx-1)){
			bool bad=1;
			int one=0,zero=0,nb=0;
			comp[id[i]].erase(comp[id[i]].find(degree[i]));
			for(auto it:vec[i]){
				comp[id[i]].erase(comp[id[i]].find(degree[it]));
				degree[it]--;
				if(!degree[it])zero++;
				//else if(degree[it]==2)nb--;
				comp[id[i]].insert(degree[it]);
			}
			if(sz(comp[id[i]])<=2)bad=0;
			else if((*comp[id[i]].begin())<=2){
				t++;
				nb=gimme(i);
				auto it=comp[id[i]].lower_bound(1);
				while(it!=comp[id[i]].end()){
					if(*it)one++;
					else break;
					it++;
				}
				/*cerr<<"deg : "<<degree[i]<<"\n";
				cerr<<i<<" "<<one<<" "<<zero<<"\n";*/
				if(!(one&1) && ((one/2 + zero)==nb))bad=0;
			}
			if(!bad)ans++;
			for(auto it:vec[i]){
				comp[id[i]].erase(comp[id[i]].find(degree[it]));
				degree[it]++;
				comp[id[i]].insert(degree[it]);
			}
			comp[id[i]].insert(degree[i]);
		}
		if(g)good.insert(id[i]);
	}
	//cerr<<"\n---------\n";
	return ans;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 48 ms 71188 KB Output is correct
3 Correct 52 ms 71296 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 107 ms 71160 KB Output is correct
6 Correct 377 ms 71496 KB Output is correct
7 Correct 48 ms 71416 KB Output is correct
8 Correct 48 ms 71304 KB Output is correct
9 Correct 50 ms 71416 KB Output is correct
10 Correct 52 ms 71416 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 48 ms 71188 KB Output is correct
3 Correct 52 ms 71296 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 107 ms 71160 KB Output is correct
6 Correct 377 ms 71496 KB Output is correct
7 Correct 48 ms 71416 KB Output is correct
8 Correct 48 ms 71304 KB Output is correct
9 Correct 50 ms 71416 KB Output is correct
10 Correct 52 ms 71416 KB Output is correct
11 Correct 170 ms 71572 KB Output is correct
12 Correct 3435 ms 72232 KB Output is correct
13 Correct 1127 ms 72312 KB Output is correct
14 Correct 562 ms 72056 KB Output is correct
15 Correct 1218 ms 73084 KB Output is correct
16 Correct 2029 ms 72212 KB Output is correct
17 Correct 363 ms 72056 KB Output is correct
18 Correct 966 ms 73208 KB Output is correct
19 Correct 1066 ms 72104 KB Output is correct
20 Correct 627 ms 72100 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 48 ms 71188 KB Output is correct
3 Correct 52 ms 71296 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 107 ms 71160 KB Output is correct
6 Correct 377 ms 71496 KB Output is correct
7 Correct 48 ms 71416 KB Output is correct
8 Correct 48 ms 71304 KB Output is correct
9 Correct 50 ms 71416 KB Output is correct
10 Correct 52 ms 71416 KB Output is correct
11 Correct 170 ms 71572 KB Output is correct
12 Correct 3435 ms 72232 KB Output is correct
13 Correct 1127 ms 72312 KB Output is correct
14 Correct 562 ms 72056 KB Output is correct
15 Correct 1218 ms 73084 KB Output is correct
16 Correct 2029 ms 72212 KB Output is correct
17 Correct 363 ms 72056 KB Output is correct
18 Correct 966 ms 73208 KB Output is correct
19 Correct 1066 ms 72104 KB Output is correct
20 Correct 627 ms 72100 KB Output is correct
21 Execution timed out 4059 ms 76456 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 48 ms 71188 KB Output is correct
3 Correct 52 ms 71296 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 107 ms 71160 KB Output is correct
6 Correct 377 ms 71496 KB Output is correct
7 Correct 48 ms 71416 KB Output is correct
8 Correct 48 ms 71304 KB Output is correct
9 Correct 50 ms 71416 KB Output is correct
10 Correct 52 ms 71416 KB Output is correct
11 Execution timed out 4085 ms 120656 KB Time limit exceeded
12 Halted 0 ms 0 KB -