oj.uz

Submission #84130

# Submission time Handle Problem Language Result Execution time Memory
84130 2018-11-13T09:20:13 Z alextodoran Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 3 ms 920 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)
{
    ndl[level[u]].push_back(u);
    h = max(h, level[u]);
    for(auto v : gr[u])
        if(viz[v] == 0)
        {
            viz[v] = 1;
            level[v] = level[u] + 1;
            parent[v] = u;
            dfs(v);
        }
}

vector <int> vq;

int findEgg(int N, vector < pair < int, int > > bridges)
{
    for(int i = 1; i <= N; i++)
        gr[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);
    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
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -