oj.uz

답안 #269738

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
269738 2020-08-17T09:27:37 Z Atill83 Easter Eggs (info1cup17_eastereggs) C++14
71.6 / 100
 26 ms 412 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

vector<int> adj[550];
int der[550];
int sz[550];

void dfs(int v, int par){
    sz[v] = 1;

    for(int j: adj[v]){
        if(j == par) continue;
        dfs(j, v);
        sz[v] += sz[j];
    }
}

int find_centroid(int N){
    int cur = 1, last = -1;
    dfs(cur, last);
    bool tru = 1;
    while(tru){
        tru = 0;
        for(int j: adj[cur]){
            if(j == last) continue;
            if(sz[j] > N / 2){
                last = cur;
                cur = j;
                tru = 1;
                break;
            }
        }
    }
    return cur;
}
int mxDer = 0;
void dfs2(int a, int par = -1){
    mxDer = max(mxDer, der[a]);
    for(int j: adj[a]){
        if(j == par) continue;
        der[j] = der[a] + 1;
        dfs2(j, a);
    }
}





int findEgg (int N, vector<pair<int,int>> bridges)
{

    for(int i = 1; i <= N; i++){
        der[i] = 0;
        sz[i] = 0;
        adj[i].clear();
    }
    
    for(int i = 0; i < N - 1; i++){
        int u = bridges[i].first, v = bridges[i].second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int a = find_centroid(N);
    dfs2(a);
    int l = 0, r = mxDer;

    while(l < r){
        vector<int> srg;
        int m = (l + r) / 2;

        for(int j = 1; j <= N; j++){
            if(der[j] > m) continue;
            srg.push_back(j);
        }

        if(query(srg)){
            r = m;
        }else{
            l = m + 1;
        }
    }
    vector<int> dur;
    vector<int> s;

    for(int j = 1; j <= N; j++){
        if(der[j] == l) s.push_back(j);
        else if(der[j] < l) dur.push_back(j);
    }

    int ll = 0, rr = (int) s.size() - 1;

    while(ll < rr){
        int mm = (ll + rr) / 2;
        vector<int> srg = dur;
        for(int j = ll; j <= mm; j++){
            srg.push_back(s[j]);
        }

        if(query(srg)){
            rr = mm;
        }else{
            ll = mm + 1;
        }
    }
    return s[ll];
}

Subtask #1
32.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 384 KB Number of queries: 5
2 Partially correct 2 ms 384 KB Number of queries: 6
3 Partially correct 1 ms 384 KB Number of queries: 6
4 Partially correct 1 ms 384 KB Number of queries: 5

Subtask #2
26.4 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 384 KB Number of queries: 8
2 Partially correct 13 ms 412 KB Number of queries: 11
3 Partially correct 19 ms 384 KB Number of queries: 11
4 Partially correct 18 ms 384 KB Number of queries: 12

Subtask #3
13.2 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 384 KB Number of queries: 9
2 Partially correct 26 ms 384 KB Number of queries: 11
3 Partially correct 22 ms 384 KB Number of queries: 11
4 Partially correct 23 ms 384 KB Number of queries: 12