제출 #927789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927789		bachhoangxuan	Park (JOI17_park)	C++17	100 / 100	270 ms	940 KiB

park

#include "park.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1405;

namespace park{
    int N,Place[maxn],vis[maxn],a[maxn];
    vector<int> edge[maxn];
    void add(int u){
        while(true){
            memset(Place,0,sizeof(Place));
            for(int i=0;i<N;i++) Place[i]=a[i];
            Place[u]=true;
            if(Ask(0,u,Place)) break;
            int l=0,r=N-1,v=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                memset(Place,0,sizeof(Place));
                for(int i=0;i<N;i++) Place[i]=(a[i] || i<=mid);
                Place[u]=1;
                if(Ask(0,u,Place)) v=mid,r=mid-1;
                else l=mid+1;
            }
            add(v);
        }
        vector<int> root;
        root.push_back(0);
        while(!root.empty()){
            int x=root.back();root.pop_back();
            if(a[x]==3) continue;
            memset(vis,0,sizeof(vis));
            vector<int> d;
            function<void(int)> dfs = [&](int u){
                vis[u]=1;
                d.push_back(u);
                for(int v:edge[u]) if(!vis[v] && a[v]!=3) dfs(v);
            };
            dfs(x);
            memset(Place,0,sizeof(Place));
            for(int v:d) Place[v]=1;
            Place[u]=1;
            if(!Ask(min(u,x),max(u,x),Place)) continue;

            int l=0,r=(int)d.size()-1,v=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                memset(Place,0,sizeof(Place));
                for(int i=0;i<=mid;i++) Place[d[i]]=1;
                Place[u]=1;
                if(Ask(min(u,x),max(u,x),Place)) v=d[mid],r=mid-1;
                else l=mid+1;
            }

            for(int nxt:edge[v]) if(a[nxt]!=3) root.push_back(nxt);

            edge[u].push_back(v);
            edge[v].push_back(u);
            Answer(min(u,v),max(u,v));
            a[v]=3;

        }
        for(int i=0;i<N;i++) a[i]=(a[i] || (i==u));
    }
    void Detect(int T, int n) {
        a[0]=1;N=n;
        for(int i=1;i<N;i++) if(!a[i]) add(i);
    }
}


void Detect(int T, int N) {
	park::Detect(T,N);
}

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