oj.uz

Submission #286671

# Submission time Handle Problem Language Result Execution time Memory
286671 2020-08-30T17:21:22 Z amiratou Parachute rings (IOI12_rings) C++14
37 / 100
 2849 ms 185320 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]])<=1)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 44 ms 70776 KB Output is correct
2 Correct 47 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 44 ms 70904 KB Output is correct
5 Correct 49 ms 71168 KB Output is correct
6 Correct 49 ms 71356 KB Output is correct
7 Correct 45 ms 71288 KB Output is correct
8 Correct 46 ms 71288 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 47 ms 71296 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2065 ms 122780 KB Output is correct
2 Correct 1544 ms 150880 KB Output is correct
3 Correct 1755 ms 181516 KB Output is correct
4 Correct 1898 ms 170872 KB Output is correct
5 Correct 1897 ms 171448 KB Output is correct
6 Correct 2849 ms 185320 KB Output is correct
7 Correct 1703 ms 180472 KB Output is correct
8 Correct 1781 ms 164228 KB Output is correct
9 Correct 1928 ms 171060 KB Output is correct
10 Correct 1391 ms 173212 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70776 KB Output is correct
2 Correct 47 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 44 ms 70904 KB Output is correct
5 Correct 49 ms 71168 KB Output is correct
6 Correct 49 ms 71356 KB Output is correct
7 Correct 45 ms 71288 KB Output is correct
8 Correct 46 ms 71288 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 47 ms 71296 KB Output is correct
11 Incorrect 164 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 44 ms 70776 KB Output is correct
2 Correct 47 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 44 ms 70904 KB Output is correct
5 Correct 49 ms 71168 KB Output is correct
6 Correct 49 ms 71356 KB Output is correct
7 Correct 45 ms 71288 KB Output is correct
8 Correct 46 ms 71288 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 47 ms 71296 KB Output is correct
11 Incorrect 164 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 44 ms 70776 KB Output is correct
2 Correct 47 ms 71160 KB Output is correct
3 Correct 50 ms 71288 KB Output is correct
4 Correct 44 ms 70904 KB Output is correct
5 Correct 49 ms 71168 KB Output is correct
6 Correct 49 ms 71356 KB Output is correct
7 Correct 45 ms 71288 KB Output is correct
8 Correct 46 ms 71288 KB Output is correct
9 Correct 50 ms 71288 KB Output is correct
10 Correct 47 ms 71296 KB Output is correct
11 Correct 2065 ms 122780 KB Output is correct
12 Correct 1544 ms 150880 KB Output is correct
13 Correct 1755 ms 181516 KB Output is correct
14 Correct 1898 ms 170872 KB Output is correct
15 Correct 1897 ms 171448 KB Output is correct
16 Correct 2849 ms 185320 KB Output is correct
17 Correct 1703 ms 180472 KB Output is correct
18 Correct 1781 ms 164228 KB Output is correct
19 Correct 1928 ms 171060 KB Output is correct
20 Correct 1391 ms 173212 KB Output is correct
21 Incorrect 164 ms 71544 KB Output isn't correct
22 Halted 0 ms 0 KB -