oj.uz

Submission #908178

# Submission time Handle Problem Language Result Execution time Memory
908178 2024-01-16T09:09:52 Z 12345678 Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 400 ms 708 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int nx=515;
int sz, t;
vector<int> qrs, on(nx), on2(nx), nd(nx), d[nx];

void dfs(int u, int p)
{
    if (on[u]&&t>0) on2[u]=1, t--;
    for (auto v:d[u]) if (v!=p) dfs(v, u); 
}

void dfs2(int u, int p)
{
    nd[u]=on2[u];
    for (auto v:d[u]) if (v!=p) dfs2(v, u), nd[u]|=nd[v];
    if (nd[u]) qrs.push_back(u);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (int i=1; i<=N; i++) on[i]=1;
    for (int i=0; i<N-1; i++) d[bridges[i].first].push_back(bridges[i].second), d[bridges[i].second].push_back(bridges[i].first);
    while (1)
    {
        sz=0;
        for (int i=1; i<=N; i++) if (on[i]) sz++;
        if (sz==1) for (int i=1; i<=N; i++) if (on[i]) return i;
        qrs.clear(); 
        for (int i=1; i<=N; i++) on2[i]=0, nd[i]=0;
        t=sz/2;
        dfs(1, 1);
        dfs2(1, 1);
        if (query(qrs)) for (int i=1; i<=N; i++) on[i]=on2[i];
        else for (int i=1; i<=N; i++) on[i]=on[i]&&!on2[i];
    }
}

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 708 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3039 ms 508 KB Time limit exceeded
2 Halted 0 ms 0 KB -