oj.uz

답안 #339240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339240 2020-12-24T23:56:39 Z ogibogi2004 Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 1 ms 640 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
const int MAXN=520;
int st[MAXN];
vector<int>g[MAXN];
bool no[MAXN];
void dfs(int u,int par)
{
	st[u]=1;
	for(auto v:g[u])
	{
		if(v==par)continue;
		if(no[v])continue;
		dfs(v,u);
		st[u]+=st[v];
	}
}
pair<int,int>best;
void find_best_in(int u,int par,int n1)
{
	if(st[u]>=n1)
	{
		best=min(best,{st[u]-n1,u});
	}
	else return;
	for(auto v:g[u])
	{
		if(v==par)continue;
		find_best_in(v,u,n1);
	}
}
vector<int>v;
bool flag;
void make_subtree(int u,int par,int t)
{
	if(u==t)flag=1;
	if(flag)v.push_back(u);
	for(auto v:g[u])
	{
		if(v==par)continue;
		make_subtree(v,u,t);
	}
	if(u==t)flag=0;
}
bool findd(vector<int>xd1,int xd2)
{
	for(auto xd:xd1)if(xd==xd2)return 1;
	return 0;
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	for(auto xd:bridges)
	{
		g[xd.first].push_back(xd.second);
		g[xd.second].push_back(xd.first);
	}
	for(;;)
	{
		int root=0,cnt=0;
		for(int i=1;i<=N;i++)
		{
			if(no[i]==0)
			{
				root=i;cnt++;
			}
		}
		if(cnt==1)return root;
		dfs(root,0);
		best={N+1,N+1};
		find_best_in(root,0,st[root]/2);
		v.clear();
		flag=0;
		make_subtree(root,0,best.first);
		if(query(v))
		{
			for(int i=1;i<=N;i++)
			{
				if(findd(v,i)==0)
				{
					no[i]=1;
				}
			}
		}
		else
		{
			for(int i=0;i<v.size();i++)no[v[i]]=1;
		}
	}
    return N;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for(int i=0;i<v.size();i++)no[v[i]]=1;
      |                ~^~~~~~~~~

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 640 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -