oj.uz

Submission #520920

# Submission time Handle Problem Language Result Execution time Memory
520920 2022-01-31T13:21:10 Z 79brue Park (JOI17_park) C++14
20 / 100
 435 ms 1924 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];

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);

        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);

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

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

        visited[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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 296 KB Output is correct
3 Correct 4 ms 296 KB Output is correct
4 Correct 4 ms 292 KB Output is correct
5 Correct 4 ms 304 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 596 KB Output is correct
2 Correct 112 ms 432 KB Output is correct
3 Correct 159 ms 1924 KB Output is correct
4 Correct 435 ms 664 KB Output is correct
5 Correct 391 ms 640 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 300 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 432 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -