Submission #269731

#	Time	Username	Problem	Language	Result	Execution time	Memory
269731		Atill83	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	1 ms	768 KiB

eastereggs

#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;
            }
        }
    }
    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 = 0; i < N - 1; i++){
        der[i + 1] = 0;
        sz[i + 1] = 0;
        adj[i + 1].clear();
        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: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20