Submission #389277

#	Time	Username	Problem	Language	Result	Execution time	Memory
389277		cheissmart	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	1 ms	584 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 520;

unordered_set<int> G[N];
int vis[N];

void init(int n) {
    for(int i = 1; i <= n; i++) {
        G[i].clear();
    }
}

int findEgg(int n, V<pi> es) {
    init(n);
    for(pi p:es) G[p.F].insert(p.S), G[p.S].insert(p.F);
    vi q;
    for(int i = 2; i <= n; i++) if(G[i].size() == 1)
        q.PB(i);
    for(int i = 0; i < int(q.size()); i++) {
        int u = q[i];
        for(int v:G[u]) if(v != 1) {
            G[v].erase(u);
            if(G[v].size() == 1) q.PB(v);
        }
    }
    q.PB(1);
    int lb = 0, rb = n - 1;
    while(lb <= rb) {
        int mb = (lb + rb) / 2;
        vi ask;
        for(int j = 0; j <= mb; j++)
            ask.PB(q[j]);
        if(query(ask)) rb = mb - 1;
        else lb = mb + 1;
    }
    return q[lb];
}

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