oj.uz

답안 #918249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918249 2024-01-29T13:49:51 Z vjudge1 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 14 ms 976 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 732 KB Number of queries: 8
2 Correct 9 ms 976 KB Number of queries: 9
3 Correct 14 ms 740 KB Number of queries: 9
4 Correct 12 ms 740 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 756 KB Number of queries: 9
2 Correct 10 ms 732 KB Number of queries: 9
3 Correct 12 ms 732 KB Number of queries: 9
4 Correct 12 ms 752 KB Number of queries: 9