oj.uz

Submission #578238

# Submission time Handle Problem Language Result Execution time Memory
578238 2022-06-16T09:05:20 Z WongChun1234 Parachute rings (IOI12_rings) C++14
37 / 100
 2878 ms 190828 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=1000050;
int n,ord[N],par[N],cyc,cycgrp[N],cn[N];
vector<int> must,adj[N],preord;
vector<pair<int,int>> lz;
bool failed,incyc[N],vis[N];
map<pair<int,int>,bool> hv;

void Init(int N_) {
	n=N_;
	failed=0;
	cyc=-1;
	preord=must={};
	for (int i=0;i<n;i++) ord[i]=0,adj[i].clear(),par[i]=cycgrp[i]=i,incyc[i]=vis[i]=0,cn[i]=-1;
}

void checknode(int u){
	if (must.empty()){
		must.push_back(u);
		for (int i=0;i<3;i++) must.push_back(adj[u][i]);
	}else{
		vector<int> nw={};
		for (int i:must){
			bool ok=0;
			if (i==u) ok=1;
			for (int j=0;j<3;j++) if (i==adj[u][j]) ok=1;
			if (ok) nw.push_back(i);
		}
		must=nw;
		if (must.empty()) failed=1;
	}
}

void failnode(int u){
	vector<int> nw={};
	for (int i:must){
		bool ok=0;
		if (i==u) ok=1;
		if (ok) nw.push_back(i);
	}
	must=nw;
	if (must.empty()) failed=1;
}

int find(int u){
	return (par[u]==u?u:par[u]=find(par[u]));
}

int ff(int u){
	return (cycgrp[u]==u?u:cycgrp[u]=ff(cycgrp[u]));
}

void merge(int u,int v){
	if (cn[ff(u)]!=-1&&cn[ff(v)]!=-1&&cn[ff(u)]!=cn[ff(v)]){
		cycgrp[ff(u)]=ff(v);
		cn[ff(v)]=INT_MAX;
	}else if (cn[ff(u)]!=-1){
		cycgrp[ff(v)]=ff(u);
	}else{
		cycgrp[ff(u)]=ff(v);
	}
}

void dfs(int u,int v){
	vis[u]=1;
	preord.push_back(u);
	for (int i:adj[u]){
		if (i==v){
			incyc[v]=1;
			for (int j:preord) incyc[j]=1;
			if (must.empty()){
				must.push_back(v);
				for (int j:preord) must.push_back(j);
			}
			return;
		}else if (vis[i]) continue;
		dfs(i,v);
	}
	preord.pop_back();
}

int cnt,pp[N],ecnt[N];
int fff(int u){
	return (pp[u]==u?u:pp[u]=fff(pp[u]));
}
int cccnt=0;
int CountCritical() {
	//for (int i:must) cerr<<i<<" ";
	//cerr<<"!\n";
	int ret;
	if (failed) ret=0;
	else if (must.size()) ret=must.size();
	else ret=n;
	return ret;
	/*cnt=0;
	for (int i=0;i<n;i++){
		bool ok=1;
		for (int j=0;j<n;j++) pp[j]=j,ecnt[j]=0;
		for (auto j:lz){
			if (j.first==i||j.second==i) continue;
			if (fff(j.first)==fff(j.second)) ok=0;
			ecnt[j.first]++; ecnt[j.second]++;
			if (ecnt[j.first]>2||ecnt[j.second]>2) ok=0;
			pp[fff(j.first)]=j.second;
			if (!ok) break;
		}
		cnt+=ok;
	}
	if (ret>cnt) assert(cnt==0);
	//tle cnt!=0
	//re cnt=0
	return ret;*/
}

void Link(int u, int v) {
	hv[{u,v}]=1;
	ord[u]++; ord[v]++;
	adj[u].push_back(v); adj[v].push_back(u);
	if (failed) goto skip;
	lz.push_back({u,v});
	if (ord[u]==3){
		checknode(u);
	}else if (ord[u]>=4){
		failnode(u);
	}
	if (failed) goto skip;
	if (ord[v]==3){
		checknode(v);
	}else if (ord[v]>=4){
		failnode(v);
	}
	if (failed) goto skip;
	if (find(u)==find(v)){
		if (cyc==-1){
			adj[u].pop_back(); adj[v].pop_back();
			dfs(u,v);
			adj[u].push_back(v); adj[v].push_back(u);
			vector<int> nw={};
			for (int i:must){
				if (incyc[i]) nw.push_back(i);
			}
			must=nw;
			if (must.empty()) failed=1;
			cyc=find(u);
			for (auto i:lz){
				if (incyc[i.first]^incyc[i.second]){
					if (incyc[i.first]){
						cn[ff(i.second)]=i.first;
					}else{
						cn[ff(i.first)]=i.second;
					}
				}
				if (incyc[i.first]||incyc[i.second]) continue;
				if (ff(i.first)!=ff(i.second)){
					merge(i.first,i.second);
				}
			}
		}else if (find(cyc)==find(u)){
			//cerr<<ff(u)<<"--"<<ff(v)<<"\n";
			if (incyc[u]||incyc[v]){
				if (incyc[u]&&incyc[v]){
					failed=1;
				}else if (incyc[u]){
					if (cn[ff(v)]=INT_MAX) failed=1;
					if (cn[ff(v)]!=-1) cn[ff(v)]=INT_MAX;
					else cn[ff(v)]=u;
				}else{
					if (cn[ff(u)]=INT_MAX) failed=1;
					if (cn[ff(u)]!=-1) cn[ff(u)]=INT_MAX;
					else cn[ff(u)]=v;
				}
			}else{
				//cerr<<cn[ff(u)]<<"uwuuwuw"<<cn[ff(v)]<<"\n";
				if (cn[ff(u)]==INT_MAX||cn[ff(v)]==INT_MAX) failed=1;
				if (!(hv[{cn[ff(u)],cn[ff(v)]}]||hv[{cn[ff(v)],cn[ff(u)]}])) failed=1;
				if (ff(u)==ff(v)) failed=1;
				merge(u,v);
			}
		}else{
			failed=1;
		}
	}else{
		par[find(u)]=v;
		if (cyc!=-1){
			if (!(incyc[u]||incyc[v])) merge(u,v);
			else{
				if (incyc[u]) swap(u,v);
				if (incyc[v]){
					cn[ff(u)]=v;
				}
			}
		}
	}
	skip:;
	//cerr<<CountCritical()<<"\n";
}

/*
9 11
0 1
1 2
2 3
3 4
4 5
3 6
5 0
6 7
6 4
5 8
8 7
*/

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:165:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  165 |      if (cn[ff(v)]=INT_MAX) failed=1;
      |                   ^
rings.cpp:169:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  169 |      if (cn[ff(u)]=INT_MAX) failed=1;
      |                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24316 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 16 ms 24352 KB Output is correct
6 Correct 19 ms 24708 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 19 ms 24268 KB Output is correct
9 Correct 18 ms 24528 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 92644 KB Output is correct
2 Correct 1818 ms 129716 KB Output is correct
3 Correct 2128 ms 140480 KB Output is correct
4 Correct 2417 ms 156308 KB Output is correct
5 Correct 2878 ms 158096 KB Output is correct
6 Correct 2813 ms 190828 KB Output is correct
7 Correct 1913 ms 136776 KB Output is correct
8 Correct 2262 ms 147844 KB Output is correct
9 Correct 2400 ms 156076 KB Output is correct
10 Correct 1782 ms 149888 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24316 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 16 ms 24352 KB Output is correct
6 Correct 19 ms 24708 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 19 ms 24268 KB Output is correct
9 Correct 18 ms 24528 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Incorrect 17 ms 24532 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24316 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 16 ms 24352 KB Output is correct
6 Correct 19 ms 24708 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 19 ms 24268 KB Output is correct
9 Correct 18 ms 24528 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Incorrect 17 ms 24532 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 15 ms 24316 KB Output is correct
3 Correct 15 ms 24404 KB Output is correct
4 Correct 15 ms 23892 KB Output is correct
5 Correct 16 ms 24352 KB Output is correct
6 Correct 19 ms 24708 KB Output is correct
7 Correct 14 ms 23892 KB Output is correct
8 Correct 19 ms 24268 KB Output is correct
9 Correct 18 ms 24528 KB Output is correct
10 Correct 18 ms 24404 KB Output is correct
11 Correct 1044 ms 92644 KB Output is correct
12 Correct 1818 ms 129716 KB Output is correct
13 Correct 2128 ms 140480 KB Output is correct
14 Correct 2417 ms 156308 KB Output is correct
15 Correct 2878 ms 158096 KB Output is correct
16 Correct 2813 ms 190828 KB Output is correct
17 Correct 1913 ms 136776 KB Output is correct
18 Correct 2262 ms 147844 KB Output is correct
19 Correct 2400 ms 156076 KB Output is correct
20 Correct 1782 ms 149888 KB Output is correct
21 Incorrect 17 ms 24532 KB Output isn't correct
22 Halted 0 ms 0 KB -