oj.uz

Submission #521426

# Submission time Handle Problem Language Result Execution time Memory
521426 2022-02-02T06:12:24 Z azberjibiou Park (JOI17_park) C++17
0 / 100
 221 ms 900 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);
    if(val==1)  return;
    for(int i=s;i<=e;i++)   Place[to_check[i]]=1;
    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> tree[1400];
vector <int> euler;
void dfs(int now, int pre)
{
    euler.push_back(now);
    for(int nxt : tree[now])   if(nxt!=pre)
    {
        dfs(nxt, now);
        euler.push_back(now);
    }
}
int cnt;
int solv_par(int now, int pre)
{
    cnt++;
    int tcnt=0;
    for(int i=0;i<N;i++)    tcnt+=tree[i].size();
    //assert(tcnt==2*cnt-2);
    euler.clear();
    dfs(0, -1);
    for(int i=0;i<N;i++)    Place[i]=0;
    Place[now]=1;
    set <int> s;
    s.insert(euler.size());
    vector <int> adj;
    /*if(pre!=-1)
    {
        adj.push_back(pre);
        for(int i=0;i<euler.size();i++)    if(euler[i]==pre)   s.insert(i);
    }*/
    int cur=0;
    while(!s.empty())
    {
        int nxt=*s.begin();
        s.erase(s.begin());
        if(cur==nxt)
        {
            cur++;
            continue;
        }
        for(int i=cur;i<=nxt-1;i++) Place[euler[i]]=1;
        int check_val=Ask(min(now, euler[cur]), max(now, euler[cur]), Place);
        for(int i=cur;i<=nxt-1;i++) Place[euler[i]]=0;
        if(check_val==0)
        {
            cur=nxt+1;
            continue;
        }
        s.insert(nxt);
        int l=cur, r=nxt-1;
        while(l!=r)
        {
            int mid=(l+r)/2;
            for(int i=l;i<=mid;i++) Place[euler[i]]=1;
            int val=Ask(min(now, euler[l]), max(now, euler[l]), Place);
            for(int i=l;i<=mid;i++) Place[euler[i]]=0;
            if(val==1)  r=mid;
            else    l=mid+1;
        }
        for(int i=l+1;i<euler.size();i++) if(euler[i]==euler[l])  s.insert(i);
        adj.push_back(euler[l]);
        cur=l+1;
    }
    assert(now>=0 && now<N);
    assert(adj[0]>=0 && adj[0]<N);
    tree[now].push_back(adj[0]);
    tree[adj[0]].push_back(now);
    for(int ele : adj)
    {
        v[ele].push_back(now);
        v[now].push_back(ele);
    }
}
void Detect(int T, int n) {
    N=n;
    Chk[0]=true;
    for(int i=1;i<N;i++)    to_check.push_back(i);
    while(!to_check.empty())
    {
        for(int i=0;i<N;i++)    Place[i]=1;
        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);
        solv_par(new_check[0], -1);
        for(int i=1;i<new_check.size();i++)
        {
            solv_par(new_check[i], new_check[i-1]);
        }
        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++)
    {
        printf("%d: ", i);
        for(int ele : v[i]) printf("%d ", ele);
        printf("\n");
    }*/
    for(int i=0;i<N;i++)
    {
        for(int ele : v[i]) if(ele<i)   Answer(ele, i);
    }
}

Compilation message

park.cpp: In function 'int solv_par(int, int)':
park.cpp:93:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int i=l+1;i<euler.size();i++) if(euler[i]==euler[l])  s.insert(i);
      |                       ~^~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i=1;i<new_check.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
park.cpp: In function 'int solv_par(int, int)':
park.cpp:56:15: warning: control reaches end of non-void function [-Wreturn-type]
   56 |     set <int> s;
      |               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 900 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -