oj.uz

답안 #521203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521203 2022-02-01T08:09:49 Z 79brue Park (JOI17_park) C++14
67 / 100
 599 ms 1920 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);

    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 468 KB Wrong Answer[6]
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 599 ms 744 KB Output is correct
2 Correct 198 ms 524 KB Output is correct
3 Correct 274 ms 1920 KB Output is correct
4 Correct 557 ms 668 KB Output is correct
5 Correct 556 ms 700 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 504 KB Output is correct
2 Correct 250 ms 508 KB Output is correct
3 Correct 254 ms 460 KB Output is correct
4 Correct 220 ms 512 KB Output is correct
5 Correct 270 ms 508 KB Output is correct
6 Correct 296 ms 460 KB Output is correct
7 Correct 248 ms 508 KB Output is correct
8 Correct 249 ms 496 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 460 KB Output is correct
2 Correct 309 ms 556 KB Output is correct
3 Correct 317 ms 544 KB Output is correct
4 Correct 386 ms 564 KB Output is correct
5 Correct 347 ms 708 KB Output is correct
6 Correct 413 ms 640 KB Output is correct
7 Correct 424 ms 716 KB Output is correct
8 Correct 305 ms 564 KB Output is correct
9 Correct 355 ms 564 KB Output is correct
10 Correct 405 ms 624 KB Output is correct
11 Correct 392 ms 684 KB Output is correct
12 Correct 295 ms 600 KB Output is correct
13 Correct 430 ms 596 KB Output is correct
14 Correct 384 ms 616 KB Output is correct
15 Correct 407 ms 600 KB Output is correct
16 Correct 254 ms 460 KB Output is correct
17 Correct 551 ms 668 KB Output is correct
18 Correct 375 ms 620 KB Output is correct
19 Correct 437 ms 632 KB Output is correct
20 Correct 358 ms 564 KB Output is correct

Subtask #5
0 / 23.0

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