oj.uz

답안 #521188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521188 2022-02-01T07:50:08 Z 79brue Park (JOI17_park) C++14
67 / 100
 578 ms 1980 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 query_select(vector<int>& v){
    for(int i=0; i<n; i++) query_arr[i] = 0;
    for(auto x: v) query_arr[x] = 1;
}

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

int deg[2002];
vector<int> link[2002];
bool chk[2002][2002];

void dfs_insert(int x, int p, vector<int>& v){
    if(deg[x] < 7000) v.push_back(x);
    for(auto y: link[x]){
        if(p==y) continue;
        dfs_insert(y, x, v);
    }
}

void reorder(int x, int p = -1){
    par[x] = p;
    for(auto y: link[x]){
        if(p==y) continue;
        depth[y] = depth[x] + 1;
        reorder(y, x);
    }
}

void solve_cross(int o, int x, int p){ /// o - ... - p - x
    if(deg[x] == 7) return;

    vector<int> vec;
    dfs_insert(x, p, vec);
    if(vec.empty()) return;
    query_select(vec), query_arr[o] = query_arr[x] = 1;
    if(!Ask(min(o, x), max(o, x), query_arr)) return;

    int basel = 0, l, r, qa;

    retry:

    l = basel, r = (int)vec.size()-1, qa = (int)vec.size() - 1;
    while(l<r){
        int m = (l+r)>>1;
        memset(query_arr, 0, sizeof(query_arr));
        query_arr[x] = query_arr[o] = 1;

        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(par[checklist[i]] != p && !query_arr[par[checklist[i]]]){
                query_arr[par[checklist[i]]] = 1;
                checklist.push_back(par[checklist[i]]);
            }
        }

        if(Ask(min(o, x), max(o, x), query_arr)){
            qa = m;
            r = m-1;
        }
        else l = m+1;
    }

    if(!chk[min(o, vec[qa])][max(o, vec[qa])]){
        deg[o]++, deg[vec[qa]]++;
        chk[min(o, vec[qa])][max(o, vec[qa])] = 1;
        Answer(min(o, vec[qa]), max(o, vec[qa]));
    }

    for(auto nxt: link[vec[qa]]){
        if(nxt == par[vec[qa]]) continue;
        solve_cross(o, nxt, vec[qa]);
    }

    basel = qa+1;
    while(basel < (int)vec.size() && depth[vec[basel]] > depth[vec[qa]]) basel++;
    if(basel == (int)vec.size()) return;
    goto retry;
}

void Detect(int t, int N){
    n = N;
    assert(n>10);

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

    for(int i=1; i<n; i++){
        deg[i]++, deg[par[i]]++;
        link[par[i]].push_back(i), link[i].push_back(par[i]);
    }

    for(int i=0; i<n; i++){
        depth[i] = 0;
        reorder(i);
        for(auto j: link[i]){
            for(auto k: link[j]){
                if(k==i) continue;
                solve_cross(i, k, j);
            }
        }
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 550 ms 632 KB Output is correct
2 Correct 195 ms 492 KB Output is correct
3 Correct 278 ms 1980 KB Output is correct
4 Correct 578 ms 672 KB Output is correct
5 Correct 556 ms 812 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 460 KB Output is correct
2 Correct 246 ms 504 KB Output is correct
3 Correct 303 ms 508 KB Output is correct
4 Correct 232 ms 496 KB Output is correct
5 Correct 270 ms 504 KB Output is correct
6 Correct 258 ms 504 KB Output is correct
7 Correct 265 ms 516 KB Output is correct
8 Correct 250 ms 580 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 472 KB Output is correct
2 Correct 331 ms 544 KB Output is correct
3 Correct 320 ms 540 KB Output is correct
4 Correct 374 ms 560 KB Output is correct
5 Correct 376 ms 596 KB Output is correct
6 Correct 425 ms 664 KB Output is correct
7 Correct 406 ms 676 KB Output is correct
8 Correct 335 ms 568 KB Output is correct
9 Correct 337 ms 556 KB Output is correct
10 Correct 434 ms 588 KB Output is correct
11 Correct 387 ms 704 KB Output is correct
12 Correct 298 ms 600 KB Output is correct
13 Correct 443 ms 596 KB Output is correct
14 Correct 353 ms 624 KB Output is correct
15 Correct 401 ms 712 KB Output is correct
16 Correct 279 ms 504 KB Output is correct
17 Correct 545 ms 776 KB Output is correct
18 Correct 374 ms 608 KB Output is correct
19 Correct 438 ms 668 KB Output is correct
20 Correct 325 ms 564 KB Output is correct

Subtask #5
0 / 23.0

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