oj.uz

Submission #901511

# Submission time Handle Problem Language Result Execution time Memory
901511 2024-01-09T13:41:39 Z ivaziva Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 11 ms 1256 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

#define MAXN 520

long long n;
vector<long long> adj[MAXN];
vector<long long> nodes;
vector<int> vec;

void dfs(long long node,long long pret)
{
    nodes.push_back(node);
    long long s=adj[node].size();
    for (long long i=0;i<s;i++)
    {
        long long sled=adj[node][i];
        if (sled!=pret) dfs(sled,node);
    }
}

bool check(long long mid)
{
    for (long i=0;i<=mid;i++) vec.push_back(nodes[i]);
    long long ans=query(vec);vec.clear();
    if (ans==1) return true;
    return false;
}

int findEgg(int N, vector < pair < int, int > > bridges)
{
    n=N;nodes.clear();
    for (long long i=0;i<MAXN;i++) adj[i].clear();
    for (long long i=0;i<n-1;i++)
    {
        long long x=bridges[i].first;
        long long y=bridges[i].second;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    long long l=0;
    long long r=n-2;
    long long rez=-1;
    while (l<=r)
    {
        long long mid=(l+r)/2;
        if (mid==rez) {r=mid-1;continue;}
        if (check(mid)) {rez=mid;r=mid-1;}
        else l=mid+1;
    }
    if (rez==-1) return nodes[n-1];
    return nodes[rez];
};

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 3 ms 472 KB Number of queries: 8
2 Correct 7 ms 992 KB Number of queries: 9
3 Correct 10 ms 996 KB Number of queries: 9
4 Correct 10 ms 488 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 520 KB Number of queries: 9
2 Correct 10 ms 752 KB Number of queries: 9
3 Correct 10 ms 732 KB Number of queries: 9
4 Correct 11 ms 1256 KB Number of queries: 9