oj.uz

Submission #169498

# Submission time Handle Problem Language Result Execution time Memory
169498 2019-12-20T17:22:35 Z Rouge_Hugo Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 20 ms 376 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int>vv;
vector<int>v[600];
void dfs (int x,int p)
{
    vv.push_back(x);
    for(auto it:v[x])
    {
        if (it==p)continue;
        dfs(it,x);
    }
}
vector<int>o;
int q (int m)
{
    o.clear();
    for(int i=0;i<=m;i++)o.push_back(vv[i]);
    return query(o);
}
int findEgg(int n, vector < pair < int, int > > bridges)
{
    vv.clear();
    for(int i=0;i<n-1;i++)
    {
        int x=bridges[i].first,y=bridges[i].second;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    int st=0,end=vv.size()-1;
    while (st<end)
    {
       // cout<<st<<" "<<end<<endl;
        int m=(st+end)/2;
        if (q(m))
        {
            end=m;continue;
        }
        st=m+1;
    }
    for(int i=0;i<n+10;i++)v[i].clear();
    return vv[st];
}
/*
vector<pair<int,int>>o;
int main()
{
    int n;cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int x,y;cin>>x>>y;
        o.push_back({x,y});
    }
    cout<<findEgg(n,o);
}
*/

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Number of queries: 8
2 Correct 13 ms 248 KB Number of queries: 9
3 Correct 20 ms 248 KB Number of queries: 9
4 Correct 17 ms 252 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 248 KB Number of queries: 9
2 Correct 16 ms 248 KB Number of queries: 9
3 Correct 16 ms 356 KB Number of queries: 9
4 Correct 18 ms 248 KB Number of queries: 9