oj.uz

Submission #286675

# Submission time Handle Problem Language Result Execution time Memory
286675 2020-08-30T17:32:08 Z amiratou Parachute rings (IOI12_rings) C++14
37 / 100
 2883 ms 173176 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;
vector<int> vec[MX];
multiset<int,greater<int> > comp[MX];
bitset<MX> vis;

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){
	vis[node]=1;
	id[node]=idx;
	comp[idx].insert(degree[node]);
	for(auto it:vec[node])
		if(!vis[it])dfs(it);
}

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])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;
			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]--;
				comp[id[i]].insert(degree[it]);
			}
			if(sz(comp[id[i]])<=2)bad=0;
			else if((*comp[id[i]].begin())<=2 && comp[id[i]].find(1)!=comp[id[i]].end()){
				comp[id[i]].erase(comp[id[i]].find(1));
				bool f=0;
				if(comp[id[i]].find(1)!=comp[id[i]].end())f=1;
				comp[id[i]].insert(1);
				if(f)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 70908 KB Output is correct
2 Correct 49 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 48 ms 71160 KB Output is correct
6 Correct 53 ms 71416 KB Output is correct
7 Correct 47 ms 71288 KB Output is correct
8 Correct 47 ms 71236 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 50 ms 71288 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2063 ms 117028 KB Output is correct
2 Correct 1521 ms 141280 KB Output is correct
3 Correct 1731 ms 170216 KB Output is correct
4 Correct 1859 ms 158680 KB Output is correct
5 Correct 1902 ms 158760 KB Output is correct
6 Correct 2883 ms 173176 KB Output is correct
7 Correct 1686 ms 169156 KB Output is correct
8 Correct 1804 ms 152324 KB Output is correct
9 Correct 1896 ms 158024 KB Output is correct
10 Correct 1351 ms 160884 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70908 KB Output is correct
2 Correct 49 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 48 ms 71160 KB Output is correct
6 Correct 53 ms 71416 KB Output is correct
7 Correct 47 ms 71288 KB Output is correct
8 Correct 47 ms 71236 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 50 ms 71288 KB Output is correct
11 Incorrect 175 ms 71544 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70908 KB Output is correct
2 Correct 49 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 48 ms 71160 KB Output is correct
6 Correct 53 ms 71416 KB Output is correct
7 Correct 47 ms 71288 KB Output is correct
8 Correct 47 ms 71236 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 50 ms 71288 KB Output is correct
11 Incorrect 175 ms 71544 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70908 KB Output is correct
2 Correct 49 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 46 ms 70904 KB Output is correct
5 Correct 48 ms 71160 KB Output is correct
6 Correct 53 ms 71416 KB Output is correct
7 Correct 47 ms 71288 KB Output is correct
8 Correct 47 ms 71236 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 50 ms 71288 KB Output is correct
11 Correct 2063 ms 117028 KB Output is correct
12 Correct 1521 ms 141280 KB Output is correct
13 Correct 1731 ms 170216 KB Output is correct
14 Correct 1859 ms 158680 KB Output is correct
15 Correct 1902 ms 158760 KB Output is correct
16 Correct 2883 ms 173176 KB Output is correct
17 Correct 1686 ms 169156 KB Output is correct
18 Correct 1804 ms 152324 KB Output is correct
19 Correct 1896 ms 158024 KB Output is correct
20 Correct 1351 ms 160884 KB Output is correct
21 Incorrect 175 ms 71544 KB Output isn't correct
22 Halted 0 ms 0 KB -