oj.uz

Submission #84131

# Submission time Handle Problem Language Result Execution time Memory
84131 2018-11-13T09:45:43 Z alextodoran Easter Eggs (info1cup17_eastereggs) C++14
71.6 / 100
 19 ms 668 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];

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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Number of queries: 5
2 Incorrect 2 ms 324 KB Number of queries: 6
3 Incorrect 3 ms 400 KB Number of queries: 6
4 Incorrect 3 ms 416 KB Number of queries: 5

Subtask #2
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 436 KB Number of queries: 9
2 Incorrect 12 ms 608 KB Number of queries: 11
3 Incorrect 19 ms 608 KB Number of queries: 12
4 Incorrect 12 ms 608 KB Number of queries: 12

Subtask #3
13.2 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 656 KB Number of queries: 10
2 Incorrect 13 ms 668 KB Number of queries: 12
3 Incorrect 15 ms 668 KB Number of queries: 11
4 Incorrect 13 ms 668 KB Number of queries: 12