oj.uz

답안 #521184

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521184 2022-02-01T07:40:08 Z 79brue Park (JOI17_park) C++14
67 / 100
 566 ms 1996 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(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;

    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 0 ms 332 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 566 ms 648 KB Output is correct
2 Correct 190 ms 480 KB Output is correct
3 Correct 239 ms 1996 KB Output is correct
4 Correct 558 ms 688 KB Output is correct
5 Correct 549 ms 692 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 508 KB Output is correct
2 Correct 242 ms 512 KB Output is correct
3 Correct 244 ms 460 KB Output is correct
4 Correct 197 ms 492 KB Output is correct
5 Correct 259 ms 632 KB Output is correct
6 Correct 238 ms 512 KB Output is correct
7 Correct 248 ms 460 KB Output is correct
8 Correct 245 ms 512 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 468 KB Output is correct
2 Correct 320 ms 548 KB Output is correct
3 Correct 310 ms 540 KB Output is correct
4 Correct 357 ms 564 KB Output is correct
5 Correct 335 ms 548 KB Output is correct
6 Correct 402 ms 640 KB Output is correct
7 Correct 400 ms 632 KB Output is correct
8 Correct 288 ms 560 KB Output is correct
9 Correct 313 ms 552 KB Output is correct
10 Correct 366 ms 616 KB Output is correct
11 Correct 393 ms 612 KB Output is correct
12 Correct 278 ms 588 KB Output is correct
13 Correct 385 ms 596 KB Output is correct
14 Correct 352 ms 628 KB Output is correct
15 Correct 360 ms 604 KB Output is correct
16 Correct 246 ms 580 KB Output is correct
17 Correct 525 ms 668 KB Output is correct
18 Correct 366 ms 604 KB Output is correct
19 Correct 407 ms 644 KB Output is correct
20 Correct 333 ms 580 KB Output is correct

Subtask #5
0 / 23.0

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