제출 #1358920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358920		NValchanov	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	6 ms	484 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int MAXN = (1 << 9) + 10;

int n;
vector < int > adj[MAXN];
int ord[MAXN];
int timer;

void dfs(int u, int p)
{
    ord[++timer] = u;

    for(int& v : adj[u])
    {
        if(v == p)
            continue;

        dfs(v, u);
    }
}

int findEgg (int N, vector < pair < int, int > > edges)
{
    n = N;

    for(int i = 1; i <= n; i++)
    {
        adj[i].clear();
    }

    for(int i = 0; i < n - 1; i++)
    {
        adj[edges[i].first].push_back(edges[i].second);
        adj[edges[i].second].push_back(edges[i].first);
    }

    timer = 0;
    dfs(1, 1);

    int left = 1;
    int right = n - 1;
    int mid;
    int ans = -1;

    while(left <= right)
    {
        mid = left + (right - left) / 2;

        vector < int > p;

        for(int i = 1; i <= mid; i++)
        {
            p.push_back(ord[i]);
        }

        if(query(p))
        {
            right = mid - 1;
            ans = mid;
        }  
        else
        {
            left = mid + 1;
        }
    }

    if(ans == -1)
        ans = n;

    return ord[ans];
}

• 서브태스크 1: 40 / 40
• 서브태스크 2: 40 / 40
• 서브태스크 3: 20 / 20