oj.uz

답안 #521216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521216 2022-02-01T08:24:52 Z 79brue Park (JOI17_park) C++14
67 / 100
 587 ms 2012 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){
    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[o] == 7) return;

    vector<int> vec;
    dfs_insert(x, p, vec);

    int basel, l, r, qa;

    retry:

    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;

    l = 0, 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;

    vec.erase(vec.begin(), vec.begin() + basel);
    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 Correct 1 ms 332 KB Output is correct
2 Incorrect 10 ms 480 KB Wrong Answer[6]
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 532 ms 800 KB Output is correct
2 Correct 204 ms 508 KB Output is correct
3 Correct 273 ms 2012 KB Output is correct
4 Correct 553 ms 712 KB Output is correct
5 Correct 587 ms 848 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 524 KB Output is correct
2 Correct 263 ms 512 KB Output is correct
3 Correct 271 ms 520 KB Output is correct
4 Correct 224 ms 528 KB Output is correct
5 Correct 293 ms 524 KB Output is correct
6 Correct 264 ms 460 KB Output is correct
7 Correct 252 ms 588 KB Output is correct
8 Correct 278 ms 532 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 476 KB Output is correct
2 Correct 308 ms 460 KB Output is correct
3 Correct 310 ms 568 KB Output is correct
4 Correct 362 ms 580 KB Output is correct
5 Correct 344 ms 632 KB Output is correct
6 Correct 404 ms 684 KB Output is correct
7 Correct 420 ms 716 KB Output is correct
8 Correct 319 ms 592 KB Output is correct
9 Correct 330 ms 580 KB Output is correct
10 Correct 438 ms 588 KB Output is correct
11 Correct 375 ms 768 KB Output is correct
12 Correct 300 ms 620 KB Output is correct
13 Correct 401 ms 624 KB Output is correct
14 Correct 357 ms 648 KB Output is correct
15 Correct 394 ms 616 KB Output is correct
16 Correct 260 ms 460 KB Output is correct
17 Correct 538 ms 684 KB Output is correct
18 Correct 365 ms 640 KB Output is correct
19 Correct 437 ms 692 KB Output is correct
20 Correct 330 ms 596 KB Output is correct

Subtask #5
0 / 23.0

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