Submission #120548

#	Time	Username	Problem	Language	Result	Execution time	Memory
120548		shayan_p	Park (JOI17_park)	C++14	100 / 100	360 ms	796 KiB

park

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include "park.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1600;

vector<int> v[maxn], start ,vec ,vec2;
bool bad[maxn], mark[maxn], done[maxn];
int n, arr[maxn], Cnt;

/*

void Answer(int a,int b){
    cout<<"Found "<<a<<" "<<b<<endl;
}

bool mark2[maxn];
vector<int>v2[maxn];

void dfs2(int u,int *arr){
    mark2[u]=1;
    for(int y:v2[u]){
	if(mark2[y]==0 && arr[y])
	    dfs2(y,arr);
    }
}
int Ask(int a,int b,int *arr){
    assert( arr[a] && arr[b] );
    memset(mark2,0,sizeof mark2);
    dfs2(a,arr);
    return mark2[b];
}
*/
void _Answer(int a,int b){
    if(a>b) swap(a,b);
    return Answer(a,b);
}
int _Ask(int a,int b,int *arr){
    assert(a!=b && arr[a] && arr[b]);
    if(a>b) swap(a,b);
    return Ask(a,b,arr);		
}

void Dfs(int u){
    mark[u]=1;
    start.PB(u);
    for(int y:v[u]){
	if(mark[y]==0 && bad[y]==0)
	    Dfs(y);
    }
}
int Bs(int u){
    int l=-1,r=sz(start)-1;
    while(r-l > 1){
	int mid=(l+r)>>1;

	for(int i=0;i<n;i++)
	    arr[i]=0;
	for(int i=0;i<=mid;i++)
	    arr[ start[i] ]=1;
	arr[u]=1;
	
	if(_Ask(u,start[0],arr)) r=mid;
	else l=mid;
    }
    return start[r];
}
void Push(int u,int r){
    memset(mark,0,sizeof mark);
    start.clear(), Dfs(r);

    for(int i=0;i<n;i++)
	arr[i]=mark[i];
    arr[u]=arr[r]=1;
    if(_Ask(u,r,arr)==0) return;
    
    int w= Bs(u);
    _Answer(u,w), v[u].PB(w), v[w].PB(u), bad[w]=1;

    memset(mark,0,sizeof mark);
    
    vector<int>vec;
    
    for(int y:v[w]){
	if(mark[y]==0 && !bad[y]) vec.PB(y), Dfs(y);
    }
    for(int y:vec){
	Push(u,y);
    }
}
void Path(int u,int l=0,int r=sz(vec2)){
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=0;
    }
    if(_Ask(0,u,arr)) return;
    for(int i=l;i<r;i++){
	arr[ vec2[i] ]=1;
    }
    if(r-l==1) { vec.PB(vec2[l]); return; }
    int mid=(l+r)>>1;
    Path(u,l,mid), Path(u,mid,r);
}

void Detect(int _,int n){
    srand(time(0));
    ::n=n;
    
    done[0]=1, Cnt=1;
    
    while(Cnt<n){
	int id=rand()%(n-Cnt);
	
	for(int i=0;i<n;i++){
	    if(done[i]) continue;
	    if(id==0){ id=i; break; }
	    id--;
	}
	
	memset(arr,0,sizeof arr);
	vec.clear(), vec2.clear();
	for(int i=0;i<n;i++){
	    arr[i]=1;
	    if(i!=id && !done[i]) vec2.PB(i);
	}
	vec.PB(id), Path(id);

	for(int i=0;i<n;i++){
	    arr[i]=0;
	}
	for(int x:vec){
	    arr[x]=1;
	}

	auto cmp=[&](int a,int b){
	    if(a==b) return false;
	    if(a==id) return false;
	    if(b==id) return true;
	    
	    arr[a]=0;
	    bool ans=_Ask(b,id,arr);
	    arr[a]=1;
	    return ans;
	};

	sort(vec.begin(), vec.end(), cmp);
	
	for(int x:vec){    
	    memset(bad,0,sizeof bad);
	    bad[x]=1;
	    Push(x,0);
	    done[x]=1;
	    Cnt++;
	}
    }
}
/*
int main(){
    int n,m; cin>>n>>m;
    while(m--){
	int a,b; cin>>a>>b;
	v2[a].PB(b), v2[b].PB(a);
    }
    Detect(-1,n);
    return 0;
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23