제출 #339773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339773		Kerim	경주 (Race) (IOI11_race)	C++17	100 / 100	452 ms	73236 KiB

race

#include "race.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,k,ans=INF;
ll dis[MAXN];
vector<PII>adj[MAXN];
set<pair<ll,int> >s[MAXN];
void dfs(int nd,int pr,int lvl){
	tr(it,adj[nd]){
		int to=it->ff;
		if(to!=pr){
			dis[to]=dis[nd]+it->ss;
			dfs(to,nd,lvl+1);	
			if((int)s[to].size()>(int)s[nd].size())
				swap(s[to],s[nd]);
			__typeof((s[nd]).begin())itt;
			tr(it,s[to])
				if(dis[nd]*2+k>=it->ff){
					itt=s[nd].lower_bound(mp(dis[nd]*2+k-it->ff,-1));
					if(itt!=s[nd].end() and itt->ff+it->ff==k+dis[nd]*2)
						umin(ans,it->ss+itt->ss-2*lvl);	
				}
			tr(it,s[to])s[nd].insert(*it);
			s[to].clear();
		}
	}
	s[nd].insert(mp(dis[nd],lvl));
	__typeof((s[nd]).begin())itt=s[nd].lower_bound(mp(k+dis[nd],-1));
	if(itt!=s[nd].end() and itt->ff-dis[nd]==k)
		umin(ans,itt->ss-lvl);
}
int best_path(int N, int K, int h[][2], int l[]){
	n=N,k=K;
	for(int i=0;i<n-1;i++){
		int u=h[i][0],v=h[i][1];
		adj[u].pb(mp(v,l[i]));
		adj[v].pb(mp(u,l[i]));	
	}dfs(1,-1,0);if(ans==INF)ans=-1;
	return ans;
}
/*
static int N, K;
static int H[MAXN][2];
static int L[MAXN];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input(){
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main(){
  freopen("grader.in.3","r",stdin);
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

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