제출 #1122230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122230		I_love_Banu	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	17 ms	756 KiB

eastereggs

#include"bits/stdc++.h"
#include"grader.h"
using namespace std;

using vi = vector<int>;

const int mxN = 513;

vi aj[mxN];
vi line;

void dfs(int u, int p = 0) {
    line.push_back(u);
    for (int v : aj[u]) {
        if (p ^ v) {
            dfs(v, u);
        }
    }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (pair<int,int> edge : bridges) {
        int u, v;
        tie(u, v) = edge;
        aj[u].push_back(v);
        aj[v].push_back(u);
    }

    dfs(1);

    int l = 0, r = N - 1;
    while (l < r) {
        int mi = (l + r) / 2;
        vi qry;
        for (int i = 0; i <= mi; i ++) {
            qry.push_back(line[i]);
        }
        if (query(qry)) {
            r = mi;
        } else {
            l = mi + 1;
        }
    }

    for (int i = 1; i <= N; i ++) {
        aj[i].clear();
    }
    line.clear();

    return line[l];
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20