제출 #270351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270351		Kewo	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	47 ms	48216 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);

int n, mark[N];
vector<int> v[N], ar;
queue<int> q;

void bfs() {
	q.push(1);
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		if(mark[x])
			continue;
		ar.pb(x);
		mark[x] = 1;
		for(auto i : v[x])
			if(!mark[i])
				q.push(i);
	}
}

bool check(int x) {
	vector<int> vec;
	for(int i = 0; i < x; i++)
		vec.pb(ar[i]);
	return query(vec);
}

int bs(int x, int y) {
	if(x == y)
		return  x;
	if(x + 1 == y) {
		if(check(x))
			return x;
		return y;
	}

	if(check(mid))
		return bs(x, mid);
	else
		return bs(mid + 1, y);
}

int findEgg (int _N, vector < pair < int, int > > bridges)
{
	n = _N;
	for(auto i : bridges) {
		v[i.fi].pb(i.se);
		v[i.se].pb(i.fi);
	}
	bfs();
	return bs(1, n);
}

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