oj.uz

Submission #363533

# Submission time Handle Problem Language Result Execution time Memory
363533 2021-02-06T13:06:19 Z denkendoemeer Park (JOI17_park) C++14
100 / 100
 568 ms 780 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 9 ms 364 KB Output is correct
4 Correct 20 ms 492 KB Output is correct
5 Correct 41 ms 492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 760 KB Output is correct
2 Correct 172 ms 620 KB Output is correct
3 Correct 238 ms 748 KB Output is correct
4 Correct 566 ms 748 KB Output is correct
5 Correct 545 ms 748 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 492 KB Output is correct
2 Correct 319 ms 492 KB Output is correct
3 Correct 306 ms 492 KB Output is correct
4 Correct 283 ms 492 KB Output is correct
5 Correct 317 ms 492 KB Output is correct
6 Correct 289 ms 620 KB Output is correct
7 Correct 294 ms 708 KB Output is correct
8 Correct 331 ms 492 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 492 KB Output is correct
2 Correct 338 ms 696 KB Output is correct
3 Correct 346 ms 620 KB Output is correct
4 Correct 382 ms 492 KB Output is correct
5 Correct 391 ms 620 KB Output is correct
6 Correct 390 ms 748 KB Output is correct
7 Correct 442 ms 620 KB Output is correct
8 Correct 342 ms 492 KB Output is correct
9 Correct 343 ms 748 KB Output is correct
10 Correct 427 ms 576 KB Output is correct
11 Correct 389 ms 716 KB Output is correct
12 Correct 326 ms 748 KB Output is correct
13 Correct 471 ms 748 KB Output is correct
14 Correct 364 ms 620 KB Output is correct
15 Correct 451 ms 492 KB Output is correct
16 Correct 291 ms 492 KB Output is correct
17 Correct 541 ms 748 KB Output is correct
18 Correct 373 ms 748 KB Output is correct
19 Correct 494 ms 620 KB Output is correct
20 Correct 376 ms 620 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 620 KB Output is correct
2 Correct 391 ms 768 KB Output is correct
3 Correct 323 ms 492 KB Output is correct
4 Correct 416 ms 748 KB Output is correct
5 Correct 371 ms 492 KB Output is correct
6 Correct 512 ms 748 KB Output is correct
7 Correct 408 ms 780 KB Output is correct
8 Correct 461 ms 628 KB Output is correct
9 Correct 409 ms 620 KB Output is correct
10 Correct 354 ms 620 KB Output is correct
11 Correct 369 ms 620 KB Output is correct
12 Correct 418 ms 620 KB Output is correct
13 Correct 358 ms 568 KB Output is correct
14 Correct 394 ms 776 KB Output is correct
15 Correct 370 ms 620 KB Output is correct
16 Correct 304 ms 620 KB Output is correct
17 Correct 568 ms 620 KB Output is correct
18 Correct 365 ms 708 KB Output is correct