Submission #1283795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283795		Faisal_Saqib	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	281 ms	196608 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
// #include "grader.cpp"
using namespace std;
const int AN=530;
vector<int> adj[AN];
vector<int> cur;
int n;
void dfs(int x,int p=-1)
{
    cur.push_back(x);
    for(auto y:adj[x])
    {
        if(y==p)continue;
        dfs(y,x);
    }
}
bool check(int len)
{
    vector<int> tp(begin(cur),begin(cur)+len+1);
    // cout<<"Asking tp: ";for(auto x:tp)cout<<x<<' ';
    // cout<<endl;
    bool r=query(tp);
    // cout<<"Result r: "<<r<<endl;
    return r;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        adj[bridges[i].first].push_back(bridges[i].second);
        adj[bridges[i].second].push_back(bridges[i].first);
    }
    dfs(1);
    int l=-1,r=cur.size()-1;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            // cout<<"ASKED ";
            // for(int j=0;j<=mid;j++)
            // {
            //     cout<<cur[j]<<' ';
            // }
            // cout<<endl;
            r=mid;
        }
        else
        {
            l=mid;
        }
    }
    // cout<<l<<' '<<r<<endl;
    return cur[r];
}

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20