Submission #71279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71279	2018-08-24T09:55:13 Z	Kmcode	Simurgh (IOI17_simurgh)	C++14	Compilation error	0 ms	0 KB

simurgh

    #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
    struct UF{
    	int belong[MAX];
    	int sz[MAX];
    	int col[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){
    		a=root(a);
    		b=root(b);
    		if(a==b)return;
    		if(a>b)swap(a,b);
    		belong[a]=b;
    		sz[b]+=sz[a];
    	}
    };
    namespace solver{
    	const int white=503;
    	const int black=504;
    	vector<pair<int,int> > v;
    	vector<pair<int,int> > g[MAX];
    	int id[MAX];
    	int pr[MAX];
    	int dep[MAX];
    	UF uf;
    	vector<int> road;
    	vector<int> swa;
    	
    	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 ask(){
    		return count_common_roads(road);
    	}
    	void make_tree(){
    		//random_shuffle(v.begin(),v.end());
    		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){
    			uf.merge(tree1,tree2);
    			return;
    		}
    		if(ret>0){
    			uf.merge(black,tree2);
    			uf.merge(white,tree1);
    			return;
    		}
    		uf.merge(black,tree1);
    		uf.merge(white,tree2);
    	}
    	std::vector<int> find_roads(int n, std::vector<int> u1, std::vector<int> v1) {
    		for(int i=0;i<u1.size();i++){
    			v.push_back(make_pair(u1[i],v1[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;
    		for(int i=0;i<v.size();i++){
    			if(uf.root(i)==black){
    				ans.push_back(i);
    			}
    		}
    		return ans;
    	}
    	
    }

Compilation message

simurgh.cpp: In function 'void solver::make_tree()':
simurgh.cpp:60:20: 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:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<u1.size();i++){
                   ~^~~~~~~~~~
simurgh.cpp:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int i=0;i<road.size();i++){
                    ~^~~~~~~~~~~~
simurgh.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<v.size();i++){
                   ~^~~~~~~~~
simurgh.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<v.size();i++){
                   ~^~~~~~~~~
/tmp/cc5ZeM42.o: In function `main':
grader.cpp:(.text.startup+0x31f): undefined reference to `find_roads(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status