oj.uz

Submission #520862

# Submission time Handle Problem Language Result Execution time Memory
520862 2022-01-31T09:20:02 Z azberjibiou Park (JOI17_park) C++17
20 / 100
 2000 ms 8888 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)
{
    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:95:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         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 1 ms 328 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 464 KB Output is correct
2 Correct 72 ms 508 KB Output is correct
3 Correct 102 ms 504 KB Output is correct
4 Correct 212 ms 508 KB Output is correct
5 Correct 205 ms 476 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 8740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 8888 KB Time limit exceeded
2 Halted 0 ms 0 KB -