oj.uz

Submission #576501

# Submission time Handle Problem Language Result Execution time Memory
576501 2022-06-13T06:49:47 Z MEGalodon Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 22 ms 468 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define MAXN 513

using namespace std;

vector<int> adj_lst[MAXN];
vector<int> dfsOrder;
int it = 0;

void dfs(int i, int p){
    if( it ) return;
    dfsOrder.push_back(i);
    for( int j : adj_lst[i] ){
        if( j == p ) continue;
        dfs(j, i);
    }
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    //for( int i{1} ; i <= N ; ++i ) adj_lst[i].clear();
    for( auto e : bridges ){
        if( it ) break;
        adj_lst[e.first].push_back(e.second);
        adj_lst[e.second].push_back(e.first);
    }
    //dfsOrder.clear();
    dfs(1, 0);
    it = 1;
    int l = 0, r = N-1;
    int m; vector<int> q;
    //for( int x : dfsOrder ) cout<<x<<" "; cout<<'\n';
    while( l < r ){
        m = (l+r)/2;
        q.clear(); q.assign(dfsOrder.begin(), dfsOrder.begin()+m+1);
        if(query(q)) r = m;
        else l = m+1;
    }
    //cout<<l<<'\n';
    return dfsOrder[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 3 ms 208 KB Number of queries: 4
4 Correct 3 ms 244 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Number of queries: 8
2 Correct 11 ms 356 KB Number of queries: 9
3 Correct 22 ms 336 KB Number of queries: 9
4 Correct 15 ms 348 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 456 KB Number of queries: 9
2 Correct 17 ms 352 KB Number of queries: 9
3 Correct 16 ms 344 KB Number of queries: 9
4 Correct 15 ms 468 KB Number of queries: 9