oj.uz

Submission #520925

# Submission time Handle Problem Language Result Execution time Memory
520925 2022-01-31T13:33:32 Z 79brue Park (JOI17_park) C++14
77 / 100
 487 ms 1972 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];
bool inRecursion[2002];

void solve(int x){
    inRecursion[x] = 1;
    /// 현재 방문한 곳만으로 접근 가능한지 판별
    for(int i=0; i<n; 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(!inRecursion[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 204 KB Output is correct
3 Correct 3 ms 328 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 588 KB Output is correct
2 Correct 163 ms 468 KB Output is correct
3 Correct 197 ms 1972 KB Output is correct
4 Correct 487 ms 604 KB Output is correct
5 Correct 432 ms 588 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 332 KB Output is correct
2 Correct 182 ms 556 KB Output is correct
3 Correct 193 ms 468 KB Output is correct
4 Correct 153 ms 460 KB Output is correct
5 Correct 210 ms 468 KB Output is correct
6 Correct 192 ms 464 KB Output is correct
7 Correct 172 ms 460 KB Output is correct
8 Correct 181 ms 460 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 404 KB Output is correct
2 Correct 229 ms 492 KB Output is correct
3 Correct 221 ms 508 KB Output is correct
4 Correct 267 ms 452 KB Output is correct
5 Correct 263 ms 460 KB Output is correct
6 Correct 313 ms 600 KB Output is correct
7 Correct 307 ms 592 KB Output is correct
8 Correct 228 ms 520 KB Output is correct
9 Correct 258 ms 508 KB Output is correct
10 Correct 326 ms 560 KB Output is correct
11 Correct 311 ms 596 KB Output is correct
12 Correct 256 ms 460 KB Output is correct
13 Correct 311 ms 556 KB Output is correct
14 Correct 277 ms 584 KB Output is correct
15 Correct 327 ms 540 KB Output is correct
16 Correct 184 ms 580 KB Output is correct
17 Correct 439 ms 616 KB Output is correct
18 Correct 288 ms 576 KB Output is correct
19 Correct 331 ms 560 KB Output is correct
20 Correct 255 ms 528 KB Output is correct

Subtask #5
0 / 23.0

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