Submission #286702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
286702	2020-08-30T18:27:34 Z	amiratou	Parachute rings (IOI12_rings)	C++14	37 / 100	2838 ms	177920 KB

rings

#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++;
				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(N<=5000){
					nb=gimme(i);
					if(!(one&1) && ((one/2 + zero)==nb))bad=0;
				}
				else if(!(one&1))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	48 ms	70784 KB	Output is correct
2	Correct	50 ms	71288 KB	Output is correct
3	Correct	53 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	108 ms	71160 KB	Output is correct
6	Correct	378 ms	71672 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	51 ms	71288 KB	Output is correct
9	Correct	53 ms	71416 KB	Output is correct
10	Correct	52 ms	71288 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1999 ms	118264 KB	Output is correct
2	Correct	1564 ms	145788 KB	Output is correct
3	Correct	1756 ms	175224 KB	Output is correct
4	Correct	1897 ms	163816 KB	Output is correct
5	Correct	1952 ms	163708 KB	Output is correct
6	Correct	2838 ms	177920 KB	Output is correct
7	Correct	1719 ms	174072 KB	Output is correct
8	Correct	1812 ms	157140 KB	Output is correct
9	Correct	1957 ms	163128 KB	Output is correct
10	Correct	1379 ms	165936 KB	Output is correct

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	70784 KB	Output is correct
2	Correct	50 ms	71288 KB	Output is correct
3	Correct	53 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	108 ms	71160 KB	Output is correct
6	Correct	378 ms	71672 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	51 ms	71288 KB	Output is correct
9	Correct	53 ms	71416 KB	Output is correct
10	Correct	52 ms	71288 KB	Output is correct
11	Correct	175 ms	71544 KB	Output is correct
12	Incorrect	891 ms	72236 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	70784 KB	Output is correct
2	Correct	50 ms	71288 KB	Output is correct
3	Correct	53 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	108 ms	71160 KB	Output is correct
6	Correct	378 ms	71672 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	51 ms	71288 KB	Output is correct
9	Correct	53 ms	71416 KB	Output is correct
10	Correct	52 ms	71288 KB	Output is correct
11	Correct	175 ms	71544 KB	Output is correct
12	Incorrect	891 ms	72236 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	70784 KB	Output is correct
2	Correct	50 ms	71288 KB	Output is correct
3	Correct	53 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	108 ms	71160 KB	Output is correct
6	Correct	378 ms	71672 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	51 ms	71288 KB	Output is correct
9	Correct	53 ms	71416 KB	Output is correct
10	Correct	52 ms	71288 KB	Output is correct
11	Correct	1999 ms	118264 KB	Output is correct
12	Correct	1564 ms	145788 KB	Output is correct
13	Correct	1756 ms	175224 KB	Output is correct
14	Correct	1897 ms	163816 KB	Output is correct
15	Correct	1952 ms	163708 KB	Output is correct
16	Correct	2838 ms	177920 KB	Output is correct
17	Correct	1719 ms	174072 KB	Output is correct
18	Correct	1812 ms	157140 KB	Output is correct
19	Correct	1957 ms	163128 KB	Output is correct
20	Correct	1379 ms	165936 KB	Output is correct
21	Correct	175 ms	71544 KB	Output is correct
22	Incorrect	891 ms	72236 KB	Output isn't correct
23	Halted	0 ms	0 KB	-