Submission #116287

#	Time	Username	Problem	Language	Result	Execution time	Memory
116287		FieryPhoenix	Race (IOI11_race)	C++11	100 / 100	560 ms	33004 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
#define INF 200001
#define MOD 1000000007

int N,K;
int H[200001][2];
int L[200001];
int subsize[200001];
vector<pair<int,int>>adj[200001];
bool dead[200001];
int dp[1000001]; //min edges to obtain length i
int temp[1000001];
int ans=INF;

int dfs(int node, int par){
  subsize[node]=1;
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par)
      subsize[node]+=dfs(v,node);
  }
  return subsize[node];
}

int dfs(int node, int par, int size){
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par && subsize[v]>size/2)
      return dfs(v,node,size);
  }
  return node;
}

vector<int>vec;
vector<int>vec2;

void dfs2(int node, int par, int numEdges, ll dis){
  if (dis>K)
    return;
  vec.push_back(dis);
  vec2.push_back(dis);
  temp[dis]=min(temp[dis],(int)numEdges);
  for (int i=0;i<(int)adj[node].size();i++){
    int v=adj[node][i].first;
    if (!dead[v] && v!=par)
      dfs2(v,node,numEdges+1,dis+adj[node][i].second);
  }
}

void solve(int node){
  int size=dfs(node,node);
  int centroid=dfs(node,node,size);
  dead[centroid]=true;
  for (int i=0;i<(int)vec2.size();i++)
    dp[vec2[i]]=INF;
  vec2.clear();
  for (int i=0;i<(int)adj[centroid].size();i++){
    int v=adj[centroid][i].first;
    if (!dead[v]){
      dfs2(v,centroid,1,adj[centroid][i].second);
      for (int j=0;j<(int)vec.size();j++)
	ans=min(ans,temp[vec[j]]+dp[K-vec[j]]);
      for (int j=0;j<(int)vec.size();j++){
	dp[vec[j]]=min(dp[vec[j]],temp[vec[j]]);
	temp[vec[j]]=INF;
      }
      vec.clear();
    }
  }
  for (int i=0;i<(int)adj[centroid].size();i++){
    int v=adj[centroid][i].first;
    if (!dead[v])
      solve(v);
  }
}

int best_path(int n, int k, int H[][2], int L[]){
  N=n;
  K=k;
  for (int i=0;i+1<N;i++){
    adj[H[i][0]].push_back({H[i][1],L[i]});
    adj[H[i][1]].push_back({H[i][0],L[i]});
  }
  for (int i=1;i<=K;i++)
    dp[i]=INF;
  for (int i=1;i<=K;i++)
    temp[i]=INF;
  solve(0);
  if (ans==INF)
    return -1;
  else
    return ans;
}

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