Submission #60653

#	Time	Username	Problem	Language	Result	Execution time	Memory
60653		Diuven	Park (JOI17_park)	C++11	10 / 100	52 ms	11516 KiB

park

#include "park.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
#include <assert.h>
#include <map>
using namespace std;
typedef pair<int, int> pii;

static int full[1500];

int n;

void add_edge(int x, int y){
    if(x>y) swap(x,y);
    assert(x!=y);
    Answer(x,y);
}
int my_ask(int a, int b, int Arr[]){
    if(a>b) swap(a,b);
    // cout<<a<<' '<<b<<'\n';
    assert(a!=b && Arr[a] && Arr[b]);
    return Ask(a,b,Arr);
}

void solve1(){
    int P[250]={};
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++){
            P[i]=P[j]=1;
            if(my_ask(i,j,P)) Answer(i,j);
            P[i]=P[j]=0;
        }
}

vector<int> G[1500];
int nu[1500], now;
bool done[1500];
int Arr[1500]={};

void fill_line(int u, int v){
    // cout<<u<<' '<<v<<'\n';

    for(int i=0; i<n; i++) Arr[i]=0;
    Arr[u]=Arr[v]=1;
    if(my_ask(u,v,Arr)){
        add_edge(u,v);
        G[u].push_back(v);
        G[v].push_back(u);
        return;
    }

    vector<int> W;
    for(int i=0; i<n; i++) if(!done[i]) W.push_back(i);
    int s=0, e=W.size()-1;
    while(s<e){
        int m=(s+e)/2;
        for(int i=0; i<=m; i++) Arr[W[i]]=1;
        int res=my_ask(u, v, Arr);
        for(int i=0; i<=m; i++) Arr[W[i]]=0;
        if(res) e=m;
        else s=m+1;
    }
    int t=W[s]; W.clear();
    done[t]=true;
    fill_line(u, t);
    fill_line(t, v);
}

void dfs(int v, int p=-1){
    nu[v]=++now;
    for(int x:G[v]) if(x!=p) dfs(x,v);
}

void solve2(){
    done[0]=true;
    for(int i=1; i<n; i++){
        if(done[i]) continue;

        vector<int> V;
        for(int i=0; i<n; i++) if(done[i]) V.push_back(i);

        int Arr[1500]={};
        for(int j=0; j<n; j++) Arr[j]=!done[j];

        now=0; dfs(V[0], -1);
        int s=0, e=V.size()-1U;
        while(s<e){
            int m=(s+e)/2;
            for(int j=0; j<=m; j++) Arr[V[j]]=1;
            int res=my_ask(V[m], i, Arr);
            for(int j=0; j<=m; j++) Arr[V[j]]=0;
            if(res) e=m;
            else s=m+1;
        }

        // for(int i=0; i<n; i++) cout<<done[i]<<' ';
        // cout<<'\n';
        done[i]=true;
        fill_line(V[s], i);
    }
}

void Detect(int T, int _n) {
    n=_n;
    for(int i=0; i<n; i++) full[i]=1;
    if(T==1) solve1();
    if(2<=T && T<=4) solve2();
}

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