oj.uz

Submission #762476

# Submission time Handle Problem Language Result Execution time Memory
762476 2023-06-21T12:27:42 Z beepbeepsheep Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 14 ms 360 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int maxn=520;
vector<short> adj[maxn];
vector<short> v;
int ptr;
vector<int> q;
void dfs(short x, short p){
    v.emplace_back(x);
    for (auto u:adj[x]){
        if (u==p) continue;
        dfs(u,x);
    }
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    for (int i=0;i<maxn;i++) adj[i].clear();
    v.clear();
    q.clear();
    ptr=0;
    for (auto [u,v]:bridges){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1,-1);
    int l=0,r=N,m;
    while (l!=r-1){
        m=(l+r)>>1;
        while (ptr<m){
            q.emplace_back(v[ptr++]);
        }
        while (ptr>m){
            q.pop_back();
            ptr--;
        }
        if (query(q)) r=m;
        else l=m;
    }
    return v[l];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Number of queries: 8
2 Correct 8 ms 356 KB Number of queries: 9
3 Correct 12 ms 356 KB Number of queries: 9
4 Correct 12 ms 352 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 336 KB Number of queries: 9
2 Correct 12 ms 360 KB Number of queries: 9
3 Correct 12 ms 336 KB Number of queries: 9
4 Correct 11 ms 352 KB Number of queries: 9