oj.uz

Submission #521228

# Submission time Handle Problem Language Result Execution time Memory
521228 2022-02-01T08:58:23 Z 79brue Park (JOI17_park) C++14
100 / 100
 581 ms 1988 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;
    vector<int> checklist;

    retry:

    if(vec.empty()) return;
    memset(query_arr, 0, sizeof(query_arr));
    query_arr[o] = query_arr[x] = 1;
    checklist.clear();

    for(auto x: vec){
        checklist.push_back(x);
        query_arr[x] = 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)) 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;

        checklist.clear();
        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);
//        if(i==49){
//            puts("");
//        }
        for(auto j: link[i]){
            for(auto k: link[j]){
                if(k==i) continue;
                solve_cross(i, k, j);
            }
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 14 ms 476 KB Output is correct
3 Correct 10 ms 420 KB Output is correct
4 Correct 18 ms 792 KB Output is correct
5 Correct 28 ms 808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 692 KB Output is correct
2 Correct 214 ms 560 KB Output is correct
3 Correct 294 ms 1988 KB Output is correct
4 Correct 555 ms 708 KB Output is correct
5 Correct 581 ms 724 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 532 KB Output is correct
2 Correct 300 ms 540 KB Output is correct
3 Correct 283 ms 520 KB Output is correct
4 Correct 255 ms 516 KB Output is correct
5 Correct 315 ms 528 KB Output is correct
6 Correct 304 ms 540 KB Output is correct
7 Correct 267 ms 644 KB Output is correct
8 Correct 280 ms 540 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 452 KB Output is correct
2 Correct 340 ms 556 KB Output is correct
3 Correct 368 ms 572 KB Output is correct
4 Correct 382 ms 700 KB Output is correct
5 Correct 395 ms 588 KB Output is correct
6 Correct 436 ms 688 KB Output is correct
7 Correct 454 ms 676 KB Output is correct
8 Correct 359 ms 592 KB Output is correct
9 Correct 394 ms 564 KB Output is correct
10 Correct 464 ms 716 KB Output is correct
11 Correct 411 ms 632 KB Output is correct
12 Correct 336 ms 696 KB Output is correct
13 Correct 456 ms 616 KB Output is correct
14 Correct 385 ms 656 KB Output is correct
15 Correct 456 ms 844 KB Output is correct
16 Correct 298 ms 520 KB Output is correct
17 Correct 556 ms 724 KB Output is correct
18 Correct 409 ms 620 KB Output is correct
19 Correct 463 ms 708 KB Output is correct
20 Correct 380 ms 588 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 1088 KB Output is correct
2 Correct 346 ms 948 KB Output is correct
3 Correct 319 ms 596 KB Output is correct
4 Correct 413 ms 964 KB Output is correct
5 Correct 354 ms 804 KB Output is correct
6 Correct 547 ms 1044 KB Output is correct
7 Correct 441 ms 964 KB Output is correct
8 Correct 427 ms 924 KB Output is correct
9 Correct 439 ms 924 KB Output is correct
10 Correct 362 ms 1212 KB Output is correct
11 Correct 397 ms 876 KB Output is correct
12 Correct 388 ms 864 KB Output is correct
13 Correct 342 ms 600 KB Output is correct
14 Correct 367 ms 856 KB Output is correct
15 Correct 431 ms 996 KB Output is correct
16 Correct 292 ms 536 KB Output is correct
17 Correct 576 ms 680 KB Output is correct
18 Correct 418 ms 696 KB Output is correct