oj.uz

Submission #822975

# Submission time Handle Problem Language Result Execution time Memory
822975 2023-08-12T06:21:04 Z Darren0724 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 16 ms 392 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
vector<int> v;
vector<vector<int>> adj;
void dfs(int k,int pa){
    v.push_back(k);
    for(int j:adj[k]){
        if(j==pa)continue;
        dfs(j,k);
    }
}
int findEgg (int n, vector<pair<int,int>> bridges)
{
    v.clear();
    adj.clear();
    adj.resize(n+1);
    for(auto [a,b]:bridges){
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1,1);
    int l=0,r=n;
    while(r-l>1){
        int m=(l+r)>>1;
        vector<int> a(v.begin(),v.begin()+m);
        if(query(a)){
            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 368 KB Number of queries: 8
2 Correct 10 ms 372 KB Number of queries: 9
3 Correct 15 ms 336 KB Number of queries: 9
4 Correct 13 ms 364 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 392 KB Number of queries: 9
2 Correct 15 ms 356 KB Number of queries: 9
3 Correct 13 ms 368 KB Number of queries: 9
4 Correct 15 ms 352 KB Number of queries: 9