oj.uz

Submission #71348

# Submission time Handle Problem Language Result Execution time Memory
71348 2018-08-24T11:16:59 Z Kmcode Simurgh (IOI17_simurgh) C++14
30 / 100
 735 ms 119700 KB 
#include<bits/stdc++.h>
//#include "books.h"
using namespace std;

//#include "simurgh.h"
int count_common_roads(const std::vector<int>& r);

#define MAX 512*512
const int white=MAX-3;
const int black=MAX-2;
int dd[601][601];

struct UF{
	int belong[MAX];
	int sz[MAX];
	int col[MAX];
	vector<int> z[MAX];
	UF(){
		memset(belong,-1,sizeof(belong));
		for(int i=0;i<MAX;i++)sz[i]=1;
	}
	inline int root(int b){
		if(belong[b]==-1){
			return b;
		}
		return belong[b]=root(belong[b]);
	}
	void merge(int a,int b){
		int ta=a;
		int tb=b;
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(a>b)swap(a,b);
		belong[a]=b;
		for(int el:z[a]){
			z[b].push_back(el);
		}
		z[a].clear();
		sz[b]+=sz[a];
	}
};
UF uf;
struct UFb{
	int belong[MAX];
	int sz[MAX];
	int col[MAX];
	vector<int> z[MAX];
	UFb(){
		memset(belong,-1,sizeof(belong));
		for(int i=0;i<MAX;i++)sz[i]=1;
	}
	inline int root(int b){
		if(belong[b]==-1){
			return b;
		}
		return belong[b]=root(belong[b]);
	}
	void merge(int a,int b){
		int ta=a;
		int tb=b;
		a=root(a);
		b=root(b);
		if(a==b)return;
		if(root(black)==a||root(black)==b){
			for(int el1:z[a]){
				if(el1>=600)continue;
				for(int el2:z[b]){
					if(el2>=600)continue;
					if(ta==el1&&tb==el2)continue;
					if(dd[el1][el2]==-1)continue;
					uf.merge(white,dd[el1][el2]);
				}
			}
		}
		if(a>b)swap(a,b);
		belong[a]=b;
		for(int el:z[a]){
			z[b].push_back(el);
		}
		z[a].clear();
		sz[b]+=sz[a];
	}
};
namespace solver{
	vector<pair<int,int> > v;
	vector<pair<int,int> > g[MAX];
	int id[MAX];
	int pr[MAX];
	int dep[MAX];
	vector<int> road;
	vector<int> swa;
	UFb bl;
	inline void dfs(int b,int pr2=-1,int d=0){
		dep[b]=d;
			for(auto go:g[b]){
				if(go.first==pr2)continue;
				dfs(go.first,b,d+1);
				pr[go.first]=b;
				id[go.first]=go.second;
			}
	}
	int ini;
	int cn;
	int ask(){
		cn++;
		return count_common_roads(road);
	}
	void make_tree(){
		UF uf2;
		for(int i=0;i<v.size();i++){
			swa.push_back(-1);
			if(uf2.root(v[i].first)!=uf2.root(v[i].second)){
				uf2.merge(v[i].first,v[i].second);
				g[v[i].first].push_back(make_pair(v[i].second,i) );
				g[v[i].second].push_back(make_pair(v[i].first,i) );
				road.push_back(i);
				swa[i]=road.size()-1;
			}
		}
		ini=ask();
	}
	int query(int exp,int add){
		road[swa[exp]]=add;
		int z=ask();
		road[swa[exp]]=exp;
		return z-ini;
	}
	inline void check(int tree1,int tree2){
		int r1=uf.root(tree1);
		int r2=uf.root(tree2);
		if(r1==r2)return;
		if(r1==black||r1==white){
			if(r2==black||r2==white){
				return;
			}
		}
		int ret=query(tree1,tree2);
		if(ret==0){
			if(r1==black){
				for(int el:uf.z[uf.root(tree2)]){
					if(el!=black)bl.merge(v[el].first,v[el].second);
				}
			}
			else{
				for(int el:uf.z[uf.root(tree1)]){
					if(el!=black)bl.merge(v[el].first,v[el].second);
				}
			}
			uf.merge(tree1,tree2);
			return;
		}
		if(ret>0){
			//bl.merge(v[tree2].first,v[tree2].second);
			for(int el:uf.z[uf.root(tree2)]){
					if(el!=black)bl.merge(v[el].first,v[el].second);
			}
			uf.merge(black,tree2);
			uf.merge(white,tree1);
			return;
		}
		//bl.merge(v[tree1].first,v[tree1].second);
		for(int el:uf.z[uf.root(tree1)]){
					if(el!=black)bl.merge(v[el].first,v[el].second);
		}
		uf.merge(black,tree1);
		uf.merge(white,tree2);
	}
	vector<int> mer[MAX];
	std::vector<int> find_roads(int n, std::vector<int> u1, std::vector<int> v1) {
		memset(dd,-1,sizeof(dd));
		for(int i=0;i<u1.size();i++){
			v.push_back(make_pair(u1[i],v1[i]));
			dd[u1[i]][v1[i]]=i;
			dd[v1[i]][u1[i]]=i;
		}
		for(int i=0;i<MAX;i++){
			bl.z[i].push_back(i);
			uf.z[i].push_back(i);
		}
		make_tree();
		if(ini==n-1){
			return road;
		}
		if(ini==0){
			for(int i=0;i<road.size();i++){
				uf.merge(road[i],white);
			}
		}
		dfs(0);
		for(int i=0;i<v.size();i++){
			if(dep[v[i].first]>dep[v[i].second])swap(v[i].first,v[i].second);
			if(pr[v[i].second]==v[i].first)continue;
			int a=v[i].first;
			int b=v[i].second;
			while(a!=b){
				if(dep[a]<dep[b]){
					check(id[b],i);
					b=pr[b];
				}
				else{
					check(id[a],i);
					a=pr[a];
				}
			}
		}
		vector<int> ans;
		UF uf2;
		for(int i=0;i<v.size();i++){
			if(uf.root(i)==black){
				ans.push_back(i);
				uf2.merge(v[i].first,v[i].second);
			}
		}
		for(int i=0;i<v.size();i++){
			mer[uf.root(i)].push_back(i);
		}
		/*for(int i=0;i<v.size();i++){
			if(i==white||i==black)continue;
			//mergeable
			if(mer[i].size()==0)continue;
			UF uf3;
			bool ok=false;
			for(int el:mer[i]){
				int a=v[el].first;
				int b=v[el].second;
				if(uf3.root(a)==uf3.root(b)){
					ok=true;
					break;
				}
				uf3.merge(a,b);
				if(uf2.root(a)==uf2.root(b)){
					ok=true;
					break;
				}
			}
			if(ok==false){
				for(int el:mer[i]){
					road.push_back(el);
					int a=v[el].first;
					int b=v[el].second;
					//uf2.merge(a,b);
				}
			}
		}*/
		//assert(ans.size()>=n-1);
		//if(bl.sz[bl.root(0)]!=n)while(1);
		return ans;
	}
	
}


std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	return solver::find_roads(n,u,v);
}

Compilation message

simurgh.cpp: In member function 'void UF::merge(int, int)':
simurgh.cpp:29:7: warning: unused variable 'ta' [-Wunused-variable]
   int ta=a;
       ^~
simurgh.cpp:30:7: warning: unused variable 'tb' [-Wunused-variable]
   int tb=b;
       ^~
simurgh.cpp: In function 'void solver::make_tree()':
simurgh.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> solver::find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:172:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<u1.size();i++){
               ~^~~~~~~~~~
simurgh.cpp:186:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<road.size();i++){
                ~^~~~~~~~~~~~
simurgh.cpp:191:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:209:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
simurgh.cpp:215:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 63480 KB correct
2 Correct 95 ms 63496 KB correct
3 Correct 84 ms 63668 KB correct
4 Correct 90 ms 63668 KB correct
5 Correct 95 ms 63668 KB correct
6 Correct 91 ms 63668 KB correct
7 Correct 75 ms 63668 KB correct
8 Correct 87 ms 63700 KB correct
9 Correct 69 ms 63700 KB correct
10 Correct 88 ms 63700 KB correct
11 Correct 92 ms 63700 KB correct
12 Correct 91 ms 63700 KB correct
13 Correct 85 ms 63700 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 63480 KB correct
2 Correct 95 ms 63496 KB correct
3 Correct 84 ms 63668 KB correct
4 Correct 90 ms 63668 KB correct
5 Correct 95 ms 63668 KB correct
6 Correct 91 ms 63668 KB correct
7 Correct 75 ms 63668 KB correct
8 Correct 87 ms 63700 KB correct
9 Correct 69 ms 63700 KB correct
10 Correct 88 ms 63700 KB correct
11 Correct 92 ms 63700 KB correct
12 Correct 91 ms 63700 KB correct
13 Correct 85 ms 63700 KB correct
14 Correct 91 ms 63700 KB correct
15 Correct 93 ms 63700 KB correct
16 Correct 90 ms 63700 KB correct
17 Correct 94 ms 63800 KB correct
18 Correct 83 ms 63800 KB correct
19 Correct 86 ms 63800 KB correct
20 Correct 90 ms 63800 KB correct
21 Correct 94 ms 63800 KB correct
22 Correct 76 ms 63800 KB correct
23 Correct 88 ms 63800 KB correct
24 Correct 79 ms 63800 KB correct
25 Correct 94 ms 63800 KB correct
26 Correct 92 ms 63800 KB correct
27 Correct 89 ms 63800 KB correct
28 Correct 83 ms 63800 KB correct
29 Correct 116 ms 63800 KB correct
30 Correct 95 ms 63800 KB correct
31 Correct 87 ms 63800 KB correct
32 Correct 90 ms 63800 KB correct
33 Correct 101 ms 63800 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 63480 KB correct
2 Correct 95 ms 63496 KB correct
3 Correct 84 ms 63668 KB correct
4 Correct 90 ms 63668 KB correct
5 Correct 95 ms 63668 KB correct
6 Correct 91 ms 63668 KB correct
7 Correct 75 ms 63668 KB correct
8 Correct 87 ms 63700 KB correct
9 Correct 69 ms 63700 KB correct
10 Correct 88 ms 63700 KB correct
11 Correct 92 ms 63700 KB correct
12 Correct 91 ms 63700 KB correct
13 Correct 85 ms 63700 KB correct
14 Correct 91 ms 63700 KB correct
15 Correct 93 ms 63700 KB correct
16 Correct 90 ms 63700 KB correct
17 Correct 94 ms 63800 KB correct
18 Correct 83 ms 63800 KB correct
19 Correct 86 ms 63800 KB correct
20 Correct 90 ms 63800 KB correct
21 Correct 94 ms 63800 KB correct
22 Correct 76 ms 63800 KB correct
23 Correct 88 ms 63800 KB correct
24 Correct 79 ms 63800 KB correct
25 Correct 94 ms 63800 KB correct
26 Correct 92 ms 63800 KB correct
27 Correct 89 ms 63800 KB correct
28 Correct 83 ms 63800 KB correct
29 Correct 116 ms 63800 KB correct
30 Correct 95 ms 63800 KB correct
31 Correct 87 ms 63800 KB correct
32 Correct 90 ms 63800 KB correct
33 Correct 101 ms 63800 KB correct
34 Runtime error 152 ms 112588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 112588 KB correct
2 Correct 98 ms 119700 KB correct
3 Incorrect 735 ms 119700 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 63480 KB correct
2 Correct 95 ms 63496 KB correct
3 Correct 84 ms 63668 KB correct
4 Correct 90 ms 63668 KB correct
5 Correct 95 ms 63668 KB correct
6 Correct 91 ms 63668 KB correct
7 Correct 75 ms 63668 KB correct
8 Correct 87 ms 63700 KB correct
9 Correct 69 ms 63700 KB correct
10 Correct 88 ms 63700 KB correct
11 Correct 92 ms 63700 KB correct
12 Correct 91 ms 63700 KB correct
13 Correct 85 ms 63700 KB correct
14 Correct 91 ms 63700 KB correct
15 Correct 93 ms 63700 KB correct
16 Correct 90 ms 63700 KB correct
17 Correct 94 ms 63800 KB correct
18 Correct 83 ms 63800 KB correct
19 Correct 86 ms 63800 KB correct
20 Correct 90 ms 63800 KB correct
21 Correct 94 ms 63800 KB correct
22 Correct 76 ms 63800 KB correct
23 Correct 88 ms 63800 KB correct
24 Correct 79 ms 63800 KB correct
25 Correct 94 ms 63800 KB correct
26 Correct 92 ms 63800 KB correct
27 Correct 89 ms 63800 KB correct
28 Correct 83 ms 63800 KB correct
29 Correct 116 ms 63800 KB correct
30 Correct 95 ms 63800 KB correct
31 Correct 87 ms 63800 KB correct
32 Correct 90 ms 63800 KB correct
33 Correct 101 ms 63800 KB correct
34 Runtime error 152 ms 112588 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Halted 0 ms 0 KB -