제출 #226791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226791		bharat2002	경주 (Race) (IOI11_race)	C++14	100 / 100	986 ms	30456 KiB

race

/*input
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int N=2e5 + 100;
const int mod=1e9 + 7;
const int inf=1e7;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
//Trace prints the name of the variable and the value.
int k, n;vector< pii > adjlist[N];
queue<int> roots;bool cent[N];
class Cent
{		
	bool visited[N];
	int sum[N];stack<int> cvals;
	void dfs(int i)
	{
		sum[i]=1;visited[i]=1;
		for(auto j:adjlist[i])
		{
			if(visited[j.f]||cent[j.f]) continue;
			dfs(j.f);sum[i]+=sum[j.f];
		}
		cvals.push(i);
	}
	public:
	void init() {
		for(int i=1;i<=n;i++) {visited[i]=0;sum[i]=0;}
	}
	bool solve()
	{
		init();bool check=0;
		for(int i=1;i<=n;i++)
		{
			if(visited[i]||cent[i]) continue;check=1;
			dfs(i);int tot=sum[cvals.top()];int cr, mval=inf;
			while(!cvals.empty())
			{	
				int cmax=tot-sum[cvals.top()];
				for(auto j:adjlist[cvals.top()])
				{
					if(sum[j.f]>sum[cvals.top()]||cent[j.f]) continue;
					cmax=max(cmax, sum[j.f]);
				}
				if(cmax<mval) 
				{
					mval=cmax;cr=cvals.top();
				}
				cvals.pop();
			}	
			roots.push(cr);cent[cr]=1;
		}
		return check;
	}
};
int tally[N*5];int optans;
void query(int i, int p, int depth, int dist)
{
	if(dist>k) return;
	if(tally[k-dist]!=inf)
	{
		optans=min(optans, tally[k-dist] + depth);
	}
	for(auto j:adjlist[i])
	{
		if(cent[j.f]||j.f==p) continue;
		query(j.f, i, depth+1, dist+j.s);
	}
}
void update(int i, int p, int depth, int dist, int ind)
{
	if(dist>k) return;
	if(ind==0) tally[dist]=min(tally[dist], depth);
	else tally[dist]=inf;
	for(auto j:adjlist[i])
	{
		if(cent[j.f]||j.f==p) continue;
		update(j.f, i, depth+1, dist+j.s, ind);
	}
}
Cent obj;
int best_path(int NC, int K, int H[][2], int L[])
{
	n=NC;k=K;optans=inf;
	for(int i=0;i<=k;i++) tally[i]=inf;
	for(int i=1;i<=n;i++) cent[i]=0;
	for(int i=0;i<n-1;i++)
	{
		adjlist[H[i][0]+1].push_back(mp(H[i][1]+1, L[i]));adjlist[H[i][1]+1].push_back(mp(H[i][0]+1, L[i]));
	}
	tally[0]=0;int iter=0;
	while(obj.solve())
	{
		while(!roots.empty())
		{
			int cur=roots.front();
			for(auto j:adjlist[cur])
			{
				if(cent[j.f]) continue;
				query(j.f, cur, 1, j.s);update(j.f, cur, 1, j.s, 0);
			}
			for(auto j:adjlist[cur])
			{
				if(cent[j.f]) continue;
				update(j.f, cur, 1, j.s, 1);
			}
			roots.pop();
		}
	}	
	if(optans==inf) return -1;return optans;
}
/*signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int NC, K, H[N][2], L[N];
	cin>>NC>>K;
	for(int i=0;i<NC-1;i++)
	{
		cin>>H[i][0]>>H[i][1]>>L[i];
	}
	cout<<best_path(NC, K, H, L);
}*/

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

race.cpp: In member function 'bool Cent::solve()':
race.cpp:50:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(visited[i]||cent[i]) continue;check=1;
    ^~
race.cpp:50:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(visited[i]||cent[i]) continue;check=1;
                                     ^~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:125:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(optans==inf) return -1;return optans;
  ^~
race.cpp:125:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(optans==inf) return -1;return optans;
                            ^~~~~~
race.cpp:106:17: warning: unused variable 'iter' [-Wunused-variable]
  tally[0]=0;int iter=0;
                 ^~~~

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