Submission #286703

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
286703	2020-08-30T18:28:45 Z	amiratou	Parachute rings (IOI12_rings)	C++14	55 / 100	4000 ms	175936 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<=20000){
					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	47 ms	70776 KB	Output is correct
2	Correct	51 ms	71164 KB	Output is correct
3	Correct	52 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	107 ms	71184 KB	Output is correct
6	Correct	373 ms	71424 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	49 ms	71220 KB	Output is correct
9	Correct	52 ms	71292 KB	Output is correct
10	Correct	51 ms	71288 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2004 ms	117828 KB	Output is correct
2	Correct	1570 ms	143196 KB	Output is correct
3	Correct	1775 ms	172792 KB	Output is correct
4	Correct	1917 ms	161196 KB	Output is correct
5	Correct	1955 ms	161564 KB	Output is correct
6	Correct	2807 ms	175936 KB	Output is correct
7	Correct	1712 ms	172304 KB	Output is correct
8	Correct	1827 ms	155116 KB	Output is correct
9	Correct	1953 ms	161648 KB	Output is correct
10	Correct	1380 ms	164344 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	70776 KB	Output is correct
2	Correct	51 ms	71164 KB	Output is correct
3	Correct	52 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	107 ms	71184 KB	Output is correct
6	Correct	373 ms	71424 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	49 ms	71220 KB	Output is correct
9	Correct	52 ms	71292 KB	Output is correct
10	Correct	51 ms	71288 KB	Output is correct
11	Correct	173 ms	71544 KB	Output is correct
12	Correct	3476 ms	72256 KB	Output is correct
13	Correct	1131 ms	72312 KB	Output is correct
14	Correct	550 ms	72184 KB	Output is correct
15	Correct	1202 ms	73116 KB	Output is correct
16	Correct	2025 ms	72104 KB	Output is correct
17	Correct	373 ms	72184 KB	Output is correct
18	Correct	972 ms	73160 KB	Output is correct
19	Correct	1067 ms	72184 KB	Output is correct
20	Correct	624 ms	72184 KB	Output is correct

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	70776 KB	Output is correct
2	Correct	51 ms	71164 KB	Output is correct
3	Correct	52 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	107 ms	71184 KB	Output is correct
6	Correct	373 ms	71424 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	49 ms	71220 KB	Output is correct
9	Correct	52 ms	71292 KB	Output is correct
10	Correct	51 ms	71288 KB	Output is correct
11	Correct	173 ms	71544 KB	Output is correct
12	Correct	3476 ms	72256 KB	Output is correct
13	Correct	1131 ms	72312 KB	Output is correct
14	Correct	550 ms	72184 KB	Output is correct
15	Correct	1202 ms	73116 KB	Output is correct
16	Correct	2025 ms	72104 KB	Output is correct
17	Correct	373 ms	72184 KB	Output is correct
18	Correct	972 ms	73160 KB	Output is correct
19	Correct	1067 ms	72184 KB	Output is correct
20	Correct	624 ms	72184 KB	Output is correct
21	Execution timed out	4075 ms	76524 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	70776 KB	Output is correct
2	Correct	51 ms	71164 KB	Output is correct
3	Correct	52 ms	71288 KB	Output is correct
4	Correct	47 ms	70904 KB	Output is correct
5	Correct	107 ms	71184 KB	Output is correct
6	Correct	373 ms	71424 KB	Output is correct
7	Correct	49 ms	71288 KB	Output is correct
8	Correct	49 ms	71220 KB	Output is correct
9	Correct	52 ms	71292 KB	Output is correct
10	Correct	51 ms	71288 KB	Output is correct
11	Correct	2004 ms	117828 KB	Output is correct
12	Correct	1570 ms	143196 KB	Output is correct
13	Correct	1775 ms	172792 KB	Output is correct
14	Correct	1917 ms	161196 KB	Output is correct
15	Correct	1955 ms	161564 KB	Output is correct
16	Correct	2807 ms	175936 KB	Output is correct
17	Correct	1712 ms	172304 KB	Output is correct
18	Correct	1827 ms	155116 KB	Output is correct
19	Correct	1953 ms	161648 KB	Output is correct
20	Correct	1380 ms	164344 KB	Output is correct
21	Correct	173 ms	71544 KB	Output is correct
22	Correct	3476 ms	72256 KB	Output is correct
23	Correct	1131 ms	72312 KB	Output is correct
24	Correct	550 ms	72184 KB	Output is correct
25	Correct	1202 ms	73116 KB	Output is correct
26	Correct	2025 ms	72104 KB	Output is correct
27	Correct	373 ms	72184 KB	Output is correct
28	Correct	972 ms	73160 KB	Output is correct
29	Correct	1067 ms	72184 KB	Output is correct
30	Correct	624 ms	72184 KB	Output is correct
31	Execution timed out	4075 ms	76524 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-