oj.uz

답안 #428713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428713 2021-06-15T14:01:40 Z tqbfjotld Park (JOI17_park) C++14
0 / 100
 114 ms 608 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 114 ms 592 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 608 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 540 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 532 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -