oj.uz

Submission #84144

# Submission time Handle Problem Language Result Execution time Memory
84144 2018-11-13T15:23:00 Z alextodoran Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 21 ms 696 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Number of queries: 4
2 Correct 3 ms 324 KB Number of queries: 4
3 Correct 2 ms 404 KB Number of queries: 4
4 Correct 3 ms 544 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 544 KB Number of queries: 8
2 Correct 17 ms 544 KB Number of queries: 9
3 Correct 20 ms 548 KB Number of queries: 9
4 Correct 17 ms 568 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 568 KB Number of queries: 9
2 Correct 16 ms 696 KB Number of queries: 9
3 Correct 18 ms 696 KB Number of queries: 9
4 Correct 20 ms 696 KB Number of queries: 9