oj.uz

답안 #654372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654372 2022-10-31T08:05:16 Z mousey Easter Eggs (info1cup17_eastereggs) C++17
66 / 100
 16 ms 392 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ld long double
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define nl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const int M=512;
vi vc[M+5], nodes;
int sz[M+5], pa[M+5];
bool bad[M+5];

void dfs(int u, int par)
{
	sz[u]=1;
	for(auto i: vc[u])
	{
		if(i==par) continue;
		if(bad[i]) continue;
		pa[i]=u;
		dfs(i, u);
		sz[u]+=sz[i];
	}
}

int centroid_decom(int u, int size)
{
	pi p={0, 0};
	for(auto i: vc[u])
	{
		if(i==pa[u]) continue;
		if(bad[i]) continue;
		p=max(p, {sz[i], i});
	}
	if(p.f > size/2) return centroid_decom(p.s, size);
	else return u;
}

void find(int u, int pa)
{
	nodes.pb(u);
	for(auto i: vc[u])
	{
		if(i==pa) continue;
		find(i, u);
	}
}

int findEgg(int N, vip bridges)
{
	for(int i = 1; i <= N; i++) bad[i]=false, vc[i].clear();
	for(auto i: bridges)
	{
		vc[i.f].pb(i.s);
		vc[i.s].pb(i.f);
	}
	int u=1;
	while(true)
	{
		nodes.clear();
		if(N==2)
		{
			nodes.pb(u);
			int report=query(nodes);
			if(report) return u;
			else
			{
				for(auto i: vc[u])
				{
					if(!bad[i]) return i;
				}
			}
		}
		dfs(u, 0);
		pa[u]=0;
		u=centroid_decom(u, N);
		int sum=1;
		vi node;
		nodes.pb(u);
		for(auto i: vc[u])
		{
			if(i==pa[u]) continue;
			if(bad[i]) continue;
			bad[i]=true;
			sum+=sz[i];
			find(i, u);
			node.pb(i);
			if(sum>=N/3) break;
		}
		int report=query(nodes);
		N-=sum;
		N++;
		if(report)
		{
			for(auto i: vc[u])
			{
				if(!bad[i]) bad[i]^=1;
			}
			for(auto i: node)
			{
				bad[i]^=1;
			}
			N=sum;
		} 
//		for(auto i: nodes) cout << i << " ";
//		nl;
//		cout << N << " " << sum << " " << u << "\n" << flush;
//		for(int i = 1; i <= 5; i++) cout << bad[i] << " ";
//		nl;
//		cout << flush;
	}
}

Subtask #1
26.4 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 208 KB Number of queries: 5
2 Partially correct 1 ms 208 KB Number of queries: 7
3 Partially correct 1 ms 208 KB Number of queries: 8
4 Partially correct 1 ms 288 KB Number of queries: 9

Subtask #2
26.4 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 336 KB Number of queries: 9
2 Partially correct 8 ms 336 KB Number of queries: 12
3 Partially correct 13 ms 336 KB Number of queries: 12
4 Partially correct 10 ms 336 KB Number of queries: 16

Subtask #3
13.2 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 16 ms 392 KB Number of queries: 10
2 Partially correct 12 ms 336 KB Number of queries: 12
3 Partially correct 16 ms 336 KB Number of queries: 12
4 Partially correct 10 ms 336 KB Number of queries: 17