Submission #428759

#	Time	Username	Problem	Language	Result	Execution time	Memory
428759		tqbfjotld	Park (JOI17_park)	C++14	20 / 100	1468 ms	664 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> curknown;
set<int> adjl[2005];
int dep[2005];
int n;

int querything[1405];

void dfs(int node, int pa){
    for (auto x : adjl[node]){
        if (x==pa) continue;
        dep[x] = dep[node]+1;
        dfs(x,node);
    }
}
int query(int a, int b, vector<int> stuff){
    memset(querything,0,sizeof(querything));
    for (int x = 0; x<n; x++) querything[x] = 0;
    for (int x : stuff){
        querything[x] = 1;
    }
    querything[a] = 1;
    querything[b] = 1;
    if (a>b) swap(a,b);
    return Ask(a,b,querything);
}
int not_query(int a, int b, vector<int> stuff){
    memset(querything,0,sizeof(querything));
    for (int x = 0; x<n; x++) querything[x] = 1;
    for (int x : stuff){
        querything[x] = 0;
    }
    querything[a] = 1;
    querything[b] = 1;
    if (a>b) swap(a,b);
    return Ask(a,b,querything);
}
/*
4 7 6
0 3
0 6
3 1
3 2
6 5
5 4
*/

void find_lowest(int node){
  //  printf("hi %d\n",node);
    int l = 1;
    int r = -1;
    for (int x = 0; x<n; x++){
        r = max(r,dep[x]+1);
    }
    while (l+1<r){
       // printf("l = %d, r = %d\n",l,r);
        int mid = (l+r)/2;
        vector<int> stuff;
        for (int x = 1; x<n; x++){
            if (dep[x]!=0 && dep[x]==mid){
                stuff.push_back(x);
               // printf("stuff %d\n",x);
            }
        }
        int res = not_query(0,node,stuff);
        if (res==1){
            r = mid;
        }
        else l = mid;
    }
   // printf("l = %d\n",l);
    vector<int> nodes;
    for (int x = 0; x<n; x++){
        if (dep[x]==l) {nodes.push_back(x);
          //  printf("%d added \n",x);
        }
    }
    while (nodes.size()>1){
        vector<int> t;
        for (int x = 0; x<nodes.size()/2; x++){
            t.push_back(nodes[x]);
        }
        for (int x = 0; x<n; x++){
           // if (dep[x]!=0 && dep[x]<l) t.push_back(x);
        }
        if (!not_query(0,node,nodes)){
            nodes = t;
        }
        else{
            vector<int> t2;
            for (int x = nodes.size()/2; x<nodes.size(); x++){
                t2.push_back(x);
            }
            nodes = t2;
        }
    }
    int pnode = nodes[0];
   // printf("pnode = %d\n",pnode);
   vector<int> spec;
    for (auto x : adjl[pnode]){
        if (dep[x]<dep[pnode]) continue;
        if (!not_query(pnode,x,{node})){
            int num = x;
            //printf("insert %d between %d and %d\n",node,num,pnode);
            spec.push_back(num);
        }
    }
    //printf("insert %d after %d\n",node,pnode);
    adjl[pnode].insert(node);
    adjl[node].insert(pnode);
    for (int x : spec){
        adjl[x].insert(node);
        adjl[node].insert(x);
            adjl[pnode].erase(adjl[pnode].lower_bound(x));
            adjl[x].erase(adjl[x].lower_bound(pnode));
    }
}

void Detect(int T, int N) {
    if (T==1){
        for (int x = 0; x<N; x++){
            for (int y = 0; y<x; y++){
                if (query(x,y,{})){
                    Answer(y,x);
                }
            }
        }
        return;
    }
    curknown.push_back(1);
    adjl[0].insert(1);
    adjl[1].insert(0);
    dep[0] = 1;
    n = N;
    for (int x = 2; x<N; x++){
        dfs(0,-1);
            find_lowest(x);


    }
    for (int x = 0; x<N; x++){
        for (auto y : adjl[x]){
            if (x<y){
                Answer(x,y);
            }
        }
    }
}

Compilation message (stderr)

park.cpp: In function 'void find_lowest(int)':
park.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int x = 0; x<nodes.size()/2; x++){
      |                         ~^~~~~~~~~~~~~~~
park.cpp:94:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for (int x = nodes.size()/2; x<nodes.size(); x++){
      |                                          ~^~~~~~~~~~~~~

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