oj.uz

답안 #137591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137591 2019-07-28T07:08:37 Z ckodser Simurgh (IOI17_simurgh) C++14
0 / 100
 412 ms 4000 KB 
#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,CNT;


ll par[maxn];
ll findPar(ll a){
    if(par[a]==a)return a;
    par[a]=findPar(par[a]);
    return par[a];
}
ll c_c_r(vector<ll> r){
    CNT++;
    if(CNT>11000)exit(1);
    if(r.size()!=N-1)exit(1);
    for(auto v:r){
	if(v<0 || v>=M)exit(1);
    }
    sort(r.begin(),r.end());
    for(ll i=0;i<N;i++){
	par[i]=i;
    }
    for(auto e:r){
	ll a=findPar(s[e]);
	ll b=findPar(t[e]);
	if(a==b)exit(1);
    }
    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;
    if(n==2){
	vector<ll> ans;
	ans.pb(0);
	return ans;
    }
    memset(ger,-1,sizeof ger);
    s=v;
    t=u;
    ll m=v.size();
    M=m;
    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

simurgh.cpp: In function 'int c_c_r(std::vector<int>)':
simurgh.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r.size()!=N-1)exit(1);
        ~~~~~~~~^~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Runtime error 3 ms 1276 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Runtime error 3 ms 1276 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Runtime error 3 ms 1276 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB correct
2 Correct 3 ms 1400 KB correct
3 Runtime error 412 ms 4000 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1400 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Runtime error 3 ms 1276 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -