oj.uz

답안 #520922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520922 2022-01-31T13:27:25 Z 79brue Park (JOI17_park) C++14
20 / 100
 469 ms 2672 KB 
#include "park.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int query_arr[2002];

bool visited[2002];
int par[2002];
int depth[2002];

void solve(int x){
    /// 현재 방문한 곳만으로 접근 가능한지 판별
    for(int i=0; i<n-1; i++){
        query_arr[i] = visited[i];
    }
    query_arr[x] = 1;
    if(Ask(0, x, query_arr)){ /// 접근 가능
        vector<int> vec;
        for(int i=0; i<n; i++) if(visited[i]) vec.push_back(i);
        sort(vec.begin(), vec.end(), [&](int a, int b){
            return depth[a] < depth[b];
        });

        int l = 0, r = (int)vec.size()-1;
        while(l<r){
            int m = (l+r)>>1;

            memset(query_arr, 0, sizeof(query_arr));
            vector<int> checklist;
            for(int i=l; i<=m; i++){
                checklist.push_back(vec[i]);
                query_arr[vec[i]] = 1;
            }
            for(int i=0; i<(int)checklist.size(); i++){
                if(checklist[i] && !query_arr[par[checklist[i]]]){
                    checklist.push_back(par[checklist[i]]);
                    query_arr[par[checklist[i]]] = 1;
                }
            }

            query_arr[x] = 1;
            bool ret = Ask(0, x, query_arr);
            for(auto v: checklist) query_arr[v] = 0;

            if(ret) r = m;
            else l = m+1;
        }

        par[x] = vec[l];
        Answer(min(par[x], x), max(par[x], x));

        visited[x] = 1;
        depth[x] = depth[par[x]] + 1;
    }
    else{
        vector<int> vec;
        for(int i=0; i<n; i++) if(!visited[i] && x!=i) vec.push_back(i);

        int l = 0, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
        while(l<=r){
            int m = (l+r)>>1;
            for(int i=0; i<=m; i++){
                query_arr[vec[i]] = 1;
            }
            bool ret = Ask(0, x, query_arr);
            for(int i=0; i<=m; i++){
                query_arr[vec[i]] = 0;
            }

            if(ret){ /// 접근 가능 -> 줄여야 함
                qa = m;
                r = m-1;
            }
            else{
                l = m+1;
            }
        }
        solve(vec[qa]);
        solve(x);
    }
}

void Detect(int t, int N){
    n = N;
    if(t==1){
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                query_arr[i-1] = query_arr[j-1] = 1;
                if(Ask(i-1, j-1, query_arr)) Answer(i-1, j-1);
                query_arr[i-1] = query_arr[j-1] = 0;
            }
        }
        return;
    }

    visited[0] = 1;
    for(int i=1; i<n; i++){
        if(visited[i]) continue;
        solve(i);
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 4 ms 324 KB Output is correct
5 Correct 4 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 469 ms 584 KB Output is correct
2 Correct 169 ms 464 KB Output is correct
3 Correct 205 ms 1952 KB Output is correct
4 Correct 432 ms 604 KB Output is correct
5 Correct 437 ms 700 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 332 KB Output is correct
2 Runtime error 246 ms 1756 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 332 KB Output is correct
2 Runtime error 324 ms 2672 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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