Submission #908182

#	Time	Username	Problem	Language	Result	Execution time	Memory
908182		12345678	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	3072 ms	504 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int nx=515;
int sz, t, cnt;
vector<int> qrs, on(nx), on2(nx), nd(nx), d[nx];

void dfs(int u, int p)
{
    if (on[u]&&t>0) on2[u]=1, t--;
    for (auto v:d[u]) if (v!=p) dfs(v, u); 
}

void dfs2(int u, int p)
{
    nd[u]=on2[u];
    for (auto v:d[u]) if (v!=p) dfs2(v, u), nd[u]|=nd[v];
    if (nd[u]) qrs.push_back(u);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (int i=1; i<=N; i++) on[i]=1;
    for (int i=0; i<N-1; i++) d[bridges[i].first].push_back(bridges[i].second), d[bridges[i].second].push_back(bridges[i].first);
    cnt=0;
    while (cnt++<=10)
    {
        sz=0;
        for (int i=1; i<=N; i++) if (on[i]) sz++;
        if (sz==1) for (int i=1; i<=N; i++) if (on[i]) return i;
        qrs.clear(); 
        for (int i=1; i<=N; i++) on2[i]=0, nd[i]=0;
        t=sz/2;
        dfs(1, 1);
        dfs2(1, 1);
        if (query(qrs)) for (int i=1; i<=N; i++) on[i]=on2[i];
        else for (int i=1; i<=N; i++) on[i]=on[i]&&!on2[i];
    }
    return 1;
}

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