oj.uz

답안 #137571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137571 2019-07-28T06:43:04 Z ckodser Simurgh (IOI17_simurgh) C++14
0 / 100
 179 ms 4068 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];
bool hast[maxn][maxn];
ll barg,N;


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+=count_common_roads(t);
    return ans;
}	
void findHam(ll v,ll l,ll r,ll x){
    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,findCnt(v,l,mid));
    findHam(v,mid,r,findCnt(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]=count_common_roads(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(count_common_roads(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,findCnt(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]);
	    }
	}
    }
    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();
    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);
    }
    
    vector<int> r(n - 1);
	for(int i = 0; i < n - 1; i++)
		r[i] = i;
	int common = count_common_roads(r);
	if(common == n - 1)
		return r;
	r[0] = n - 1;
	return r;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Incorrect 3 ms 1272 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Incorrect 3 ms 1272 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Incorrect 3 ms 1272 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB correct
2 Correct 3 ms 1400 KB correct
3 Incorrect 179 ms 4068 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB correct
2 Correct 3 ms 1400 KB correct
3 Correct 3 ms 1400 KB correct
4 Incorrect 3 ms 1272 KB WA in grader: NO
5 Halted 0 ms 0 KB -