oj.uz

Submission #520864

# Submission time Handle Problem Language Result Execution time Memory
520864 2022-01-31T09:35:18 Z azberjibiou Park (JOI17_park) C++17
77 / 100
 368 ms 728 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

int N;
static int Place[1400];
bool Chk[1400];
int now;
vector <int> new_check;
vector <int> to_check;
vector <int> v[1400];
void solv(int s, int e)
{
    for(int i=s;i<=e;i++)   Place[to_check[i]]=0;
    int val=Ask(0, now, Place);
    for(int i=s;i<=e;i++)   Place[to_check[i]]=1;
    if(val==1)  return;
    if(s==e)
    {
        new_check.push_back(to_check[s]);
        return;
    }
    int mid=(s+e)/2;
    solv(s, mid);
    solv(mid+1, e);
}
bool cmp1(int a, int b)
{
    Place[a]=0;
    int val=Ask(0, b, Place);
    Place[a]=1;
    return val==0;
}
vector <int> euler;
void dfs(int now, int pre)
{
    euler.push_back(now);
    for(int nxt : v[now])   if(nxt!=pre)
    {
        dfs(nxt, now);
        euler.push_back(now);
    }
}
int solv_par(int now)
{
    euler.clear();
    dfs(0, -1);
    int s=0, e=euler.size()-1;
    for(int i=0;i<N;i++)    Place[i]=0;
    Place[now]=1;
    while(s!=e)
    {
        int mid=(s+e)/2;
        for(int i=s;i<=mid;i++) Place[euler[i]]=1;
        int val=Ask(min(now, euler[s]), max(now, euler[s]), Place);
        for(int i=s;i<=mid;i++) Place[euler[i]]=0;
        if(val==0)  s=mid+1;
        else    e=mid;
    }
    for(int i=0;i<N;i++)    Place[i]=1;
    return euler[s];
}
void ez_Detect(int T, int n)
{
    N=n;
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            Place[i]=1, Place[j]=1;
            if(Ask(i, j, Place))    Answer(i, j);
            Place[i]=0, Place[j]=0;
        }
    }
}
void Detect(int T, int n) {
    if(T==1)
    {
        ez_Detect(T, n);
        return;
    }
    N=n;
    for(int i=0;i<N;i++)    Place[i]=1;
    Chk[0]=true;
    for(int i=1;i<N;i++)    to_check.push_back(i);
    while(!to_check.empty())
    {
        now=to_check.back();
        to_check.pop_back();
        new_check.push_back(now);
        if(!to_check.empty())   solv(0, to_check.size()-1);
        sort(new_check.begin(), new_check.end(), cmp1);
        int par=solv_par(new_check[0]);
        v[par].push_back(new_check[0]);
        v[new_check[0]].push_back(par);
        for(int i=0;i+1<new_check.size();i++)   v[new_check[i]].push_back(new_check[i+1]), v[new_check[i+1]].push_back(new_check[i]);
        for(int ele : new_check)    Chk[ele]=true;
        new_check.clear();
        to_check.clear();
        for(int i=0;i<N;i++)    if(!Chk[i]) to_check.push_back(i);
    }
    for(int i=0;i<N;i++)
    {
        for(int ele : v[i]) if(ele<i)   Answer(ele, i);
    }
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i=0;i+1<new_check.size();i++)   v[new_check[i]].push_back(new_check[i+1]), v[new_check[i+1]].push_back(new_check[i]);
      |                     ~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 492 KB Output is correct
2 Correct 71 ms 484 KB Output is correct
3 Correct 90 ms 488 KB Output is correct
4 Correct 206 ms 460 KB Output is correct
5 Correct 202 ms 484 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 420 KB Output is correct
2 Correct 216 ms 460 KB Output is correct
3 Correct 237 ms 460 KB Output is correct
4 Correct 215 ms 448 KB Output is correct
5 Correct 264 ms 480 KB Output is correct
6 Correct 233 ms 440 KB Output is correct
7 Correct 209 ms 460 KB Output is correct
8 Correct 233 ms 456 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 420 KB Output is correct
2 Correct 322 ms 468 KB Output is correct
3 Correct 332 ms 468 KB Output is correct
4 Correct 358 ms 588 KB Output is correct
5 Correct 340 ms 464 KB Output is correct
6 Correct 212 ms 536 KB Output is correct
7 Correct 312 ms 464 KB Output is correct
8 Correct 298 ms 440 KB Output is correct
9 Correct 319 ms 572 KB Output is correct
10 Correct 253 ms 516 KB Output is correct
11 Correct 227 ms 476 KB Output is correct
12 Correct 267 ms 456 KB Output is correct
13 Correct 327 ms 460 KB Output is correct
14 Correct 237 ms 728 KB Output is correct
15 Correct 353 ms 452 KB Output is correct
16 Correct 242 ms 448 KB Output is correct
17 Correct 202 ms 508 KB Output is correct
18 Correct 259 ms 492 KB Output is correct
19 Correct 302 ms 528 KB Output is correct
20 Correct 357 ms 468 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 444 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -