Submission #428713

#	Time	Username	Problem	Language	Result	Execution time	Memory
428713		tqbfjotld	Park (JOI17_park)	C++14	0 / 100	114 ms	608 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;
    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;
    return Ask(a,b,querything);
}
/*
1 6 5
0 3
0 1
1 4
1 2
2 5
*/

void find_lowest(int node){
  //  printf("hi %d\n",node);
    int l = 0;
    int r = -1;
    for (int x = 0; x<n; x++){
        r = max(r,dep[x]);
    }
    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 = query(0,node,stuff);
        if (res==1){
            r = mid;
        }
        else l = mid;
    }
     l=r;
    //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);
    for (auto x : adjl[pnode]){
        if (dep[x]<dep[pnode]) continue;
        if (!not_query(pnode,x,{node})){
            int num = x;
            adjl[pnode].erase(adjl[pnode].lower_bound(num));
            adjl[num].erase(adjl[num].lower_bound(pnode));
            adjl[pnode].insert(node);
            adjl[num].insert(node);
            adjl[node].insert(num);
            adjl[node].insert(pnode);
           // printf("insert %d between %d and %d\n",node,num,pnode);
            return;
        }
    }
    //printf("insert %d after %d\n",node,pnode);
    adjl[pnode].insert(node);
    adjl[node].insert(pnode);
}

void Detect(int T, int N) {
    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);
        if (not_query(0,x,curknown)){
            //printf("hi %d\n",x);
            adjl[0].insert(x);
            adjl[x].insert(0);
        }
        else{
            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:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int x = 0; x<nodes.size()/2; x++){
      |                         ~^~~~~~~~~~~~~~~
park.cpp:92:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for (int x = nodes.size()/2; x<nodes.size(); x++){
      |                                          ~^~~~~~~~~~~~~

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