oj.uz

Submission #671528

# Submission time Handle Problem Language Result Execution time Memory
671528 2022-12-13T06:22:30 Z Trunkty Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 20 ms 360 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "grader.h"

vector<int> roads[515];
int nextnode=1, val[515];

void dfs(int x, int p){
    val[nextnode] = x;
    nextnode++;
    for(int i:roads[x]){
        if(i!=p){
            dfs(i,x);
        }
    }
}

int findEgg(int n, vector<pair<int,int>> bridges){
    for(pair<int,int> i:bridges){
        roads[i.first].push_back(i.second);
        roads[i.second].push_back(i.first);
    }
    dfs(1,0);
    int low=1,high=n,mid;
    while(low!=high){
        mid = (low+high)/2;
        vector<int> x;
        for(int i=1;i<=mid;i++){
            x.push_back(val[i]);
        }
        if(query(x)){
            high = mid;
        }
        else{
            low = mid+1;
        }
    }
    int ans=val[low];
    nextnode = 1;
    for(int i=1;i<=n;i++){
        roads[i].clear();
        val[i] = 0;
    }
    return ans;
}

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 348 KB Number of queries: 8
2 Correct 10 ms 336 KB Number of queries: 9
3 Correct 14 ms 340 KB Number of queries: 9
4 Correct 14 ms 336 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 352 KB Number of queries: 9
2 Correct 14 ms 356 KB Number of queries: 9
3 Correct 14 ms 360 KB Number of queries: 9
4 Correct 15 ms 344 KB Number of queries: 9