oj.uz

Submission #908193

# Submission time Handle Problem Language Result Execution time Memory
908193 2024-01-16T09:22:13 Z 12345678 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 16 ms 1024 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int nx=515;
int sz, t, cnt;
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=1; i<=N; i++) d[i].clear();
    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
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 344 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 1 ms 344 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 744 KB Number of queries: 8
2 Correct 5 ms 476 KB Number of queries: 9
3 Correct 11 ms 476 KB Number of queries: 9
4 Correct 8 ms 344 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1024 KB Number of queries: 9
2 Correct 9 ms 476 KB Number of queries: 9
3 Correct 10 ms 476 KB Number of queries: 9
4 Correct 8 ms 684 KB Number of queries: 9