답안 #1040543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1040543 2024-08-01T07:07:40 Z 정희우(#10998) The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
76 ms 12932 KB
#include <vector>
#include "incursion.h"
#include <cstdio>
#include<iostream>
#include<algorithm>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;
using vintp = vector<intp>;

const int MAX_N=45010;

int n;
vintp eg[MAX_N];
int sz[MAX_N];
vint val;
int isleaf=0;

bool compe(const intp &e1,const intp &e2)
{
	return e1.second>e2.second;
}

int fillsz(int v,int p)
{
	sz[v]=1;
	for(auto &e : eg[v])
		if(e.first!=p)
		{
			e.second=fillsz(e.first,v);
			sz[v]+=e.second;
		}
	for(auto &e : eg[v])
		if(e.first==p)
			e.second=n-sz[v];
	sort(eg[v].begin(),eg[v].end(),compe);
	return sz[v];
}

bool ismid(int v)
{
	int mx=0;
	for(auto e : eg[v])
		mx=max(mx,e.second);
	int c=0;
	for(auto e : eg[v])
		if(e.second==mx)c++;
	return c>=2;
}

void dfs(int v,int p)
{
	if(ismid(v))
	{
		val[v-1]=isleaf;
	}
	else if(p==0)
	{
		val[v-1]=0;
	}
	else
	{
		int mx=0;
		for(auto e : eg[v])
			mx=max(mx,e.second);
		for(auto e : eg[v])
			if(e.first==p)
				val[v-1]=(e.second==mx);
	}
	for(auto e : eg[v])
		if(e.first!=p)
			dfs(e.first,v);
}

vint mark(vintp F, int safe)
{
  	n=F.size()+1;
	for(int i=1;i<=n;i++)
		eg[i].clear();
	for(int i=0;i<n-1;i++)
	{
		int u=F[i].first,v=F[i].second;
		eg[u].push_back({v,0});
		eg[v].push_back({u,0});
	}
	val.resize(n);
	fillsz(safe,0);
	isleaf=(eg[safe].size()<=1);
	dfs(safe,0);
	return val;
}

bool checkleaf(int v,int p)
{
	if(isleaf==-1)return false;
	int flag=1;
	for(auto e : eg[v])
		if(e.first!=p && eg[e.first].size()>1)flag=0;
	if(flag==0)return false;
	if(isleaf==0)return true;
	for(auto e : eg[v])
		if(e.first!=p)
		{
			if(visit(e.first)==0)return true;
			visit(v);
		}
	return false;
}

void calc(int v,int p,int t)
{
	if(ismid(v))
	{
		isleaf=t;
		if(checkleaf(v,p))
			return;
		for(auto e : eg[v])
			if(e.first!=p)
			{
				int nt=visit(e.first);
				if(nt==0)
				{
					calc(e.first,v,nt);
					return;
				}
				visit(v);
			}
		return;
	}
	if(checkleaf(v,p))
		return;
	if(t==1)return calc(eg[v][0].first,v,visit(eg[v][0].first));
	if(t==0 && eg[v].size()<=1)return;
	int nt;
	if(eg[v][1].first!=p)
	{
		nt=visit(eg[v][1].first);
		if(nt==0)
		{
			calc(eg[v][1].first,v,nt);
			return;
		}
		visit(v);
	}
	nt=visit(eg[v][2].first);
	if(nt==0)
	{
		calc(eg[v][2].first,v,nt);
		return;
	}
	visit(v);
}

void locate(vintp F, int curr, int t)
{
	cout << curr << ' ';
	n=F.size()+1;
	for(int i=1;i<=n;i++)
		eg[i].clear();
	for(int i=0;i<n-1;i++)
	{
		int u=F[i].first,v=F[i].second;
		eg[u].push_back({v,0});
		eg[v].push_back({u,0});
	}
	fillsz(curr,0);
	isleaf=-1;
	calc(curr,0,t);
	return;
}

Compilation message

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2820 KB Security violation!
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 12932 KB Security violation!
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 8788 KB Security violation!
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2820 KB Security violation!
2 Halted 0 ms 0 KB -