oj.uz

Submission #918247

# Submission time Handle Problem Language Result Execution time Memory
918247 2024-01-29T13:48:55 Z Fikrat_Asadzadeh Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 13 ms 1008 KB 
#include <bits/stdc++.h> 
#include "grader.h"
using namespace std; 
typedef unsigned long long ull; 
#define ll long long
typedef vector < int > vl; 
typedef set < int > setl;
#define F first
#define S second    
#define all(v) v.begin(), v.end() 
#define pll pair < int , int > 
#define db  double
#define nll cout << "\n"
#define nl endl
#define sync                          \
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
const int MAX = 1e6 + 5; 
const long long inf = 1e18; 
vl g[550], v;
void dfs(ll u, ll par){
    v.push_back(u);
    for(auto i : g[u]){
        if(i == par)continue;
        dfs(i, u);
    }
}
int findEgg(int N, vector < pair < int, int > > bridges){ 
    v.clear();
    for(ll i = 1; i <= N; i++){
        g[i].clear();
    }
    for(pll i : bridges)g[i.first].push_back(i.second), g[i.second].push_back(i.first);
    dfs(1, 0);
    ll l = 0, r = N - 1, mid;
    while(l < r){
        mid = (l + r) >> 1;
        vl v2;
        for(ll i = 0; i <= mid; i++)v2.push_back(v[i]);
        if(query(v2))r = mid;
        else l = mid + 1;
    }
    return v[l];
}

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 736 KB Number of queries: 8
2 Correct 7 ms 740 KB Number of queries: 9
3 Correct 11 ms 992 KB Number of queries: 9
4 Correct 10 ms 736 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 772 KB Number of queries: 9
2 Correct 9 ms 728 KB Number of queries: 9
3 Correct 10 ms 984 KB Number of queries: 9
4 Correct 11 ms 1008 KB Number of queries: 9