제출 #557453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
557453		Koosha_mv	즐거운 행로 (APIO20_fun)	C++14	0 / 100	4 ms	4956 KiB

fun

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#include "fun.h"

const int N=1e5+99;

int n,rt,dist[N],col[N],SZ[N],DIST[N];
vector<int> g[N],vec[N];

void dfs1(int u,int p){
	SZ[u]=1;
	for(auto v : g[u]){
		if(v==p) continue ;
		DIST[v]=DIST[u]+1;
		dfs1(v,u);
		SZ[u]+=SZ[v];
	}
}
/*
int hoursRequired(int u,int v){
	DIST[u]=0;
	dfs1(u,u);
	return DIST[v];
}
int attractionsBehind(int u,int v){
	dfs1(u,u);
	return SZ[v];
}
*/
int cmp(int u,int v){
	return dist[u]>dist[v];
}
int get1(int u,int v){
	return hoursRequired(u,v);
}
int get2(int u,int v){
	return attractionsBehind(u,v);
}
void findcentroid(){
	int sz=n+1;
	rt=-1;
	f(i,0,n){
		int res=get2(0,i);
		if(res>=(n+1)/2 && res<sz){
			rt=i;
			sz=res;
		}
	}
}
vector<int> solve(vector<int> v0,vector<int> v1){
	vector<int> ans;
	sort(all(v0),cmp);
	sort(all(v1),cmp);
	f(i,0,v0.size()){
		ans.pb(v0[i]);
		if(i<v1.size()) ans.pb(v1[i]);
	}
	f(i,1,ans.size()) if(col[ans[i]]==col[ans[i-1]]) return {};
	ans.pb(rt);
	return ans;
}
vector<int> createFunTour(int _n, int Q) {
	vector<int> adj;
	n=_n;
	findcentroid();
	f(i,0,n){
		dist[i]=get1(rt,i);
		if(dist[i]==1) adj.pb(i);
	}
	f(i,0,n){
		if(rt==i) continue ;
		f(j,0,adj.size()){
			if(j==adj.size()-1 || dist[i]==get1(adj[j],i)+1){
				vec[j].pb(i);
				break;
			}
		}
	}
	f(i,0,2){
		f(j,0,2){
			if(vec[j].size()<vec[j+1].size()){
				swap(vec[j],vec[j+1]);
				swap(adj[j],adj[j+1]);
			}
		}
	}
	//dbgv(adj);
	//cout<<"vec0 = "; for(auto x : vec[0]) cout<<x<<" "; cout<<endl;
	//cout<<"vec1 = "; for(auto x : vec[1]) cout<<x<<" "; cout<<endl;
	//cout<<"vec2 = "; for(auto x : vec[2]) cout<<x<<" "; cout<<endl;
	f(i,0,3) for(auto x : vec[i]) col[x]=i;
	vector<int> ans,res0=vec[0],res1=vec[1];
	int x=(vec[2].size()-(vec[0].size()-vec[1].size())+1)/2,y=vec[2].size()-x;
	sort(all(vec[2]),cmp);
	f(i,0,x) res0.pb(vec[2][i]);
	f(i,x,x+y) res1.pb(vec[2][i]);
	ans=solve(res0,res1);
	if(ans.size()) return ans;
	res0=vec[0],res1=vec[1];
	f(i,0,y) res1.pb(vec[2][i]);
	f(i,y,y+x) res0.pb(vec[2][i]);
	ans=solve(res0,res1);
	if(ans.size()) return ans;
	return {};
}
/*
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin>>n;
	f(i,1,n){
		int u,v;
		//cin>>u>>v;
		u=(i-1)/2,v=i;
		g[u].pb(v);
		g[v].pb(u);
	}
	vector<int> ans=createFunTour(n,n);
	dbgv(ans);
	f(i,1,ans.size()-1){
		if(get1(ans[i-1],ans[i])<get1(ans[i],ans[i+1])){
			eror(i);
			return cout<<"FUCK",0;
		}
	}
	
}*/
/*
7
0 1
0 5
0 6
1 2
1 4
2 3
*/

컴파일 시 표준 에러 (stderr) 메시지

fun.cpp: In function 'std::vector<int> solve(std::vector<int>, std::vector<int>)':
fun.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   73 |  f(i,0,v0.size()){
      |    ~~~~~~~~~~~~~               
fun.cpp:73:2: note: in expansion of macro 'f'
   73 |  f(i,0,v0.size()){
      |  ^
fun.cpp:75:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   if(i<v1.size()) ans.pb(v1[i]);
      |      ~^~~~~~~~~~
fun.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   77 |  f(i,1,ans.size()) if(col[ans[i]]==col[ans[i-1]]) return {};
      |    ~~~~~~~~~~~~~~              
fun.cpp:77:2: note: in expansion of macro 'f'
   77 |  f(i,1,ans.size()) if(col[ans[i]]==col[ans[i-1]]) return {};
      |  ^
fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   91 |   f(j,0,adj.size()){
      |     ~~~~~~~~~~~~~~             
fun.cpp:91:3: note: in expansion of macro 'f'
   91 |   f(j,0,adj.size()){
      |   ^
fun.cpp:92:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    if(j==adj.size()-1 || dist[i]==get1(adj[j],i)+1){
      |       ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34