제출 #598350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598350		ono_de206	경주 (Race) (IOI11_race)	C++14	0 / 100	13 ms	9684 KiB

race

#include "race.h"


#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define in insert

const int mxn=2e5+10;
vector<pair<int,int> > g[mxn];
int ans=-1,n,k,vis[mxn],sub[mxn];
int cn[1000000];

int dfs(int to,int fr)
{
	sub[to]=1;
	for(auto [x,y] : g[to])
	{
		if(x==fr || vis[x]) continue;
		sub[to]+=dfs(x,to);
	}
	return sub[to];
}

int get_cen(int to,int fr,int sz)
{
	for(auto [x,y] : g[to])
	{
		if(x==fr || vis[x]) continue;
		if(sz/2<sub[x]) return get_cen(x,to,sz);
	}
	return to;
}

void up(int tmp,int cnt)
{
	if(tmp==k) 
	{
		if(ans==-1) ans=cnt;
		else ans=min(ans,cnt);
	}
	else
	{
		if(cn[k-cnt]) 
		{
			if(ans==-1) ans=cnt+cn[k-cnt];
			else ans=min(ans,cnt+cn[k-cnt]);
		}
	}
}

void dfs2(int to,int fr,int tmp,int cnt)
{
	if(tmp>k) return;
	up(tmp,cnt);
	for(auto [x,y] : g[to])
	{
		if(x==fr || vis[x]) continue;
		dfs2(x,to,tmp+y,cnt+1);
	}
}

void upd(int to,int fr,int tmp,int cnt)
{
	if(tmp>=k) return;
	cn[k-tmp]=(cn[k-tmp]==0 ? cnt : min(cn[k-tmp],cnt));
	for(auto [x,y] : g[to])
	{
		if(x==fr || vis[x]) continue;
		upd(x,to,tmp+y,cnt+1);
	}
}

void solve(int id)
{
	id=get_cen(id,-1,dfs(id,-1));
	for(auto [x,y] : g[id])
	{
		if(vis[x]) continue;
		dfs2(x,id,y,1);
		upd(x,id,y,1);
	}
	vis[id]=1;
	memset(cn,0,sizeof(cn));
	for(auto [x,y] : g[id])
	{
		if(vis[x]) continue;
		solve(x);
	}
}

int best_path(int N, int K, int h[][2], int l[])
{
	n=N;
	k=K;
	memset(vis,0,sizeof(vis));
	for(int i=0; i<N-1; i++)
	{
		g[h[i][0]].pb({h[i][1],l[i]});
		g[h[i][1]].pb({h[i][0],l[i]});
	}
	solve(0);
	return ans;
}

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

race.cpp: In function 'int dfs(int, int)':
race.cpp:20:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |  for(auto [x,y] : g[to])
      |           ^
race.cpp: In function 'int get_cen(int, int, int)':
race.cpp:30:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for(auto [x,y] : g[to])
      |           ^
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:59:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |  for(auto [x,y] : g[to])
      |           ^
race.cpp: In function 'void upd(int, int, int, int)':
race.cpp:70:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for(auto [x,y] : g[to])
      |           ^
race.cpp: In function 'void solve(int)':
race.cpp:80:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |  for(auto [x,y] : g[id])
      |           ^
race.cpp:88:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |  for(auto [x,y] : g[id])
      |           ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57