제출 #1145991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145991		ivailo_ganchev	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	8 ms	512 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define endl '\n'
using namespace std;
const int MAXN = 1024;
vector<int>e[MAXN];
vector<int>order;
int n;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
void dfs(int node, int parent)
{
    order.push_back(node);
    for(int &nb : e[node])
    {
        if(nb==parent)
            continue;
        dfs(nb, node);
    }
}
bool check(int mid)
{
    vector<int>q;
    q.clear();
    for(int i=0;i<=mid;i++)
    {
        q.push_back(order[i]);
    }
    int qAns=query(q);
    return qAns;
}
int binarySearch()
{
    int l=0,r=order.size()-1,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    return order[l];
}
void read(int N, vector < pair < int, int > > &bridges)
{
    n=N;
    for(pair <int , int>& i : bridges)
    {
        e[i.first].push_back(i.second);
        e[i.second].push_back(i.first);
    }
}
void clearMemory()
{
    for(int i=0;i<MAXN;i++)
    {
        e[i].clear();
    }
    order.clear();
}
int findEgg (int N, vector<pair<int,int>>bridges)
{
    read(N, bridges);
    dfs(1, -1);
    int ans=binarySearch();
    clearMemory();
    return ans;
}

• Subtask 1: 32 / 40
• Subtask 2: 40 / 40
• Subtask 3: 15 / 20