oj.uz

답안 #521182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521182 2022-02-01T07:27:28 Z 79brue Park (JOI17_park) C++14
67 / 100
 586 ms 1956 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] < 7) 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(!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, vec[qa], nxt);
    }

    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;

    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 561 ms 672 KB Output is correct
2 Correct 203 ms 612 KB Output is correct
3 Correct 260 ms 1956 KB Output is correct
4 Correct 586 ms 680 KB Output is correct
5 Correct 560 ms 700 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 528 KB Output is correct
2 Correct 250 ms 508 KB Output is correct
3 Correct 265 ms 520 KB Output is correct
4 Correct 222 ms 516 KB Output is correct
5 Correct 276 ms 536 KB Output is correct
6 Correct 278 ms 520 KB Output is correct
7 Correct 251 ms 524 KB Output is correct
8 Correct 256 ms 516 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 580 KB Output is correct
2 Correct 332 ms 564 KB Output is correct
3 Correct 328 ms 572 KB Output is correct
4 Correct 411 ms 588 KB Output is correct
5 Correct 346 ms 624 KB Output is correct
6 Correct 430 ms 664 KB Output is correct
7 Correct 406 ms 672 KB Output is correct
8 Correct 338 ms 640 KB Output is correct
9 Correct 327 ms 460 KB Output is correct
10 Correct 393 ms 744 KB Output is correct
11 Correct 385 ms 640 KB Output is correct
12 Correct 346 ms 620 KB Output is correct
13 Correct 407 ms 624 KB Output is correct
14 Correct 372 ms 588 KB Output is correct
15 Correct 387 ms 608 KB Output is correct
16 Correct 268 ms 660 KB Output is correct
17 Correct 546 ms 704 KB Output is correct
18 Correct 375 ms 632 KB Output is correct
19 Correct 454 ms 648 KB Output is correct
20 Correct 345 ms 708 KB Output is correct

Subtask #5
0 / 23.0

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