Submission #137585

#	Time	Username	Problem	Language	Result	Execution time	Memory
137585		ckodser	Simurgh (IOI17_simurgh)	C++14	Compilation error	0 ms	0 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=510;
const ll inf=1e9+900;

ll d[maxn];
vector<ll> s,t;
ll ger[maxn][maxn];
ll hast[maxn][maxn];
ll barg,N,M;




ll c_c_r(vector<ll> r){
    if(r.size()!=N-1)exit(1);
    for(auto v:r){
	if(v<0 || v>=M)exit(1);
    }
    sort(r.begin(),r.end());
    return count_common_roads(r);
}

ll findCnt(ll v,ll l,ll r){
    vector<ll> t;
    for(ll i=l;i<r;i++){
	if(i!=v && i!=barg){
	    t.pb(ger[v][i]);
	}
    }
    ll ans=0;
    ans-=hast[v][barg];
    t.pb(ger[v][barg]);
    for(ll i=0;i<l;i++){
	if(i!=v &&i!=barg){
	    t.pb(ger[barg][i]);
	    ans-=hast[barg][i];
	}
    }
    for(ll i=r;i<N;i++){
	if(i!=v && i!=barg){
	    t.pb(ger[barg][i]);
	    ans-=hast[barg][i];
	}
    }
    ans+=c_c_r(t);
    return ans;
}	
void findHam(ll v,ll l,ll r){
    if(l>=r)return;
    ll x=findCnt(v,l,r);
    if(x==0)return;
    if(l+1==r){
	hast[v][l]=1;
	hast[l][v]=1;
	return;
    }
    ll mid=(l+r)/2;
    findHam(v,l,mid);
    findHam(v,mid,r);
}

vector<ll> solve(ll n){
    barg=-1;
    for(ll i=0;i<n;i++){
	vector<ll> r;
	for(ll j=0;j<n;j++){
	    if(j!=i){
		r.pb(ger[i][j]);
	    }
	}
	d[i]=c_c_r(r);
	if(d[i]==1)barg=i;
    }
    for(ll i=0;i<n;i++){
	if(i!=barg){
	    vector<ll> r;
	    ll yeki=-1;
	    for(ll j=0;j<n;j++){
		if(j!=i && j!=barg){
		    yeki=j;
		    r.pb(ger[i][j]);
		}
	    }
	    r.pb(ger[barg][yeki]);

	    if(c_c_r(r)==d[i]-1){
		hast[barg][i]=1;
		hast[i][barg]=1;
		break;
	    }
	}
    }
    for(ll i=0;i<n;i++){
	if(i!=barg){
	    findHam(i,0,n);
	}
    }
    vector<ll> ans;
    for(ll i=0;i<n;i++){
	for(ll j=i+1;j<n;j++){
	    if(hast[i][j]){
		ans.pb(ger[i][j]);
	    }
	}
    }
    sort(ans.begin(),ans.end());
    if(c_c_r(ans)!=n-1){
	exit(-1);
    }
    return ans;
}
vector<int> find_roads(int n,vector<int> u,vector<int> v) {
    N=n;
    M=m;
    if(n==2){
	vector<ll> ans;
	ans.pb(0);
	return ans;
    }
    memset(ger,-1,sizeof ger);
    s=v;
    t=u;
    ll m=v.size();
    for(ll i=0;i<m;i++){
	ger[s[i]][t[i]]=i;
	ger[t[i]][s[i]]=i;
    }
    if(m==(n*(n-1))/2){
	return solve(n);
    }
    exit(1); 
}

Compilation message (stderr)

simurgh.cpp: In function 'int c_c_r(std::vector<int>)':
simurgh.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r.size()!=N-1)exit(1);
        ~~~~~~~~^~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:126:7: error: 'm' was not declared in this scope
     M=m;
       ^