Submission #84131

#	Time	Username	Problem	Language	Result	Execution time	Memory
84131		alextodoran	Easter Eggs (info1cup17_eastereggs)	C++14	71.60 / 100	19 ms	668 KiB

eastereggs

#include <bits/stdc++.h>

#define NM 520

using namespace std;

int query(vector < int > islands);

vector <int> gr[NM];
int level[NM], h;
int parent[NM];
bool viz[NM];
vector <int> ndl[NM];

void dfs(int u, int level)
{
    ndl[level].push_back(u);
    h = max(h, level);
    for(auto v : gr[u])
        if(viz[v] == 0)
        {
            viz[v] = 1;
            parent[v] = u;
            dfs(v, level + 1);
        }
}

vector <int> vq;

int findEgg(int N, vector < pair < int, int > > bridges)
{
    for(int i = 1; i <= N; i++)
    {
        gr[i].clear();
        ndl[i].clear();
    }
    for(auto e : bridges)
    {
        gr[e.first].push_back(e.second);
        gr[e.second].push_back(e.first);
    }
    memset(viz, 0, sizeof(viz));
    viz[1] = 1;
    dfs(1, 1);
    int l = 1, r = h, mid;
    while(l < r)
    {
        mid = (l + r) / 2;
        vq.clear();
        for(int i = mid; i >= 1; i--)
            for(auto u : ndl[i])
                vq.push_back(u);
        if(query(vq) == 0)
            l = mid + 1;
        else
            r = mid;
    }
    int lvl = l;
    l = 0;
    r = ndl[lvl].size() - 1;
    while(l < r)
    {
        memset(viz, 0, sizeof(viz));
        mid = (l + r) / 2;
        for(int i = l; i <= mid; i++)
            for(int u = ndl[lvl][i]; viz[u] == 0 && u > 0; u = parent[u])
                viz[u] = 1;
        vq.clear();
        for(int i = 1; i <= N; i++)
            if(viz[i] == 1)
                vq.push_back(i);
        if(query(vq) == 0)
            l = mid + 1;
        else
            r = mid;
    }
    return ndl[lvl][l];
}

• Subtask 1: 32 / 40
• Subtask 2: 26.4 / 40
• Subtask 3: 13.2 / 20