Submission #363533

#	Time	Username	Problem	Language	Result	Execution time	Memory
363533		denkendoemeer	Park (JOI17_park)	C++14	100 / 100	568 ms	780 KiB

park

#include "park.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>g[2005];
int viz[2005],c[2005],s[2005],n,u;
bool inq[2005],v[2005];
void added(int x,int y)
{
    if (x>y)
        swap(x,y);
    g[x].push_back(y);
    g[y].push_back(x);
    Answer(x,y);
}
bool query(int x,int y)
{
    if (x>y)
        swap(x,y);
    return Ask(x,y,c);
}
void dfs(int nod)
{
    s[u++]=nod;
    inq[nod]=1;
    for(auto it:g[nod])
        if (v[it] && inq[it]==0)
            dfs(it);
}
int calced(int nod)
{
    int st=0,dr=n-1,last=-1,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        int i;
        for(i=0;i<=mij;i++)
            if (viz[i]!=2)
                c[i]=1;
            else
                c[i]=0;
        for(i=mij+1;i<n;i++)
            if (viz[i]==1)
                c[i]=1;
            else
                c[i]=0;
        c[nod]=1;
        if (query(0,nod)){
            last=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return last;
}
bool init(int nod)
{
    int i;
    for(i=0;i<n;i++)
        if (viz[i]==1)
            c[i]=1;
        else
            c[i]=0;
    c[nod]=1;
    return query(0,nod);
}
void reinit(int nod)
{
    v[nod]=0;
    for(auto it:g[nod])
        if (v[it])
            reinit(it);
}
void finded(int nod)
{
    int i;
    for(i=0;i<n;i++)
        if (viz[i]==1)
            v[i]=1;
        else
            v[i]=0;
    for(i=0;i<n;i++){
        while(v[i]){
            int j;
            for(j=0;j<n;j++)
                c[j]=v[j];
            c[nod]=1;
            if (query(nod,i)==0){
                reinit(i);
                continue;
            }
            u=0;
            for(j=0;j<n;j++)
                inq[j]=0;
            dfs(i);
            int st=0,dr=u-1,last=-1,mij;
            while(st<=dr){
                mij=(st+dr)/2;
                for(j=0;j<u;j++)
                    if (j<=mij)
                        c[s[j]]=1;
                    else
                        c[s[j]]=0;
                if (query(nod,i)){
                    last=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            added(nod,s[last]);
            v[s[last]]=0;
        }
    }
}
void addcomp(int nod)
{
    viz[nod]=2;
    while(!init(nod))
        addcomp(calced(nod));
    finded(nod);
    viz[nod]=1;
}
void Detect(int t,int N)
{
    n=N;
    viz[0]=1;
    int i;
    for(i=1;i<n;i++)
        if (viz[i]==0)
            addcomp(i);
}

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