oj.uz

Submission #98486

# Submission time Handle Problem Language Result Execution time Memory
98486 2019-02-23T18:53:56 Z TAMREF Easter Eggs (info1cup17_eastereggs) C++11
100 / 100
 32 ms 384 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#include "grader.h"

using namespace std;
using pii = pair<int,int>;
vector<int> G[550];
vector<int> ord;

void dfs(int x, int p){
    ord.push_back(x);
    for(int u : G[x]){
        if(u == p) continue;
        dfs(u, x);
    }
}

bool ini = true;
int findEgg (int N, vector<pii> bridges){
    if(ini){
        for(int i = 0; i < N-1; i++){
            G[bridges[i].va].push_back(bridges[i].vb);
            G[bridges[i].vb].push_back(bridges[i].va);
        }
        dfs(1,0);
        ini = false;
    }
    int s = 0, e = N - 1, m;
    while(s < e){
        m = (s+e) >> 1;
        int qry = query(vector<int>(ord.begin(), ord.begin() + m + 1));
        //printf("bs on [%d,%d], qry = %d\n",s,e,qry);
        if(qry) e = m;
        else s = m + 1;
    }
    //printf("m = %d\n",m);
    //for(int u : ord) printf("%d ",u); puts("");
    return ord[e];
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Number of queries: 8
2 Correct 18 ms 256 KB Number of queries: 9
3 Correct 17 ms 384 KB Number of queries: 9
4 Correct 19 ms 256 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 256 KB Number of queries: 9
2 Correct 19 ms 256 KB Number of queries: 9
3 Correct 27 ms 256 KB Number of queries: 9
4 Correct 18 ms 256 KB Number of queries: 9