Submission #84144

#	Time	Username	Problem	Language	Result	Execution time	Memory
84144		alextodoran	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	21 ms	696 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];
int nd[NM];

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

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));
    level[1] = 1;
    viz[1] = 1;
    dfs(1);
    nd[0] = 0;
    for(int i = 1; i <= h; i++)
        for(auto u : ndl[i])
        {
            nd[0]++;
            nd[nd[0]] = u;
        }
    int l = 1, r = N, mid;
    while(l < r)
    {
        mid = (l + r) / 2;
        vq.clear();
        for(int i = level[nd[mid]] - 1; i >= 1; i--)
            for(auto u : ndl[i])
                vq.push_back(u);
        int d = mid - vq.size();
        for(int i = 0; i < d; i++)
            vq.push_back(ndl[level[nd[mid]]][i]);
        if(query(vq) == 0)
            l = mid + 1;
        else
            r = mid;
    }
    return nd[l];
}

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