Submission #116275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116275	2019-06-12T00:55:49 Z	FieryPhoenix	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KB

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 2001001001
#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];
ll dp[1000001]; //min edges to obtain length i
ll temp[1000001];
ll 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;
}

void dfs2(int node, int par, int numEdges, ll dis){
  if (dis<=K)
    temp[dis]=min(temp[dis],(ll)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);
  for (int i=1;i<=K;i++)
    temp[i]=INF;
  temp[0]=0;
  dead[centroid]=true;
  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=1;j<=K;j++)
	ans=min(ans,temp[j]+dp[K-j]);
      for (int j=1;j<=K;j++)
	dp[j]=min(dp[j],temp[j]);
    }
  }
  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[][], 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;
  solve(0);
  if (ans==INF)
    return -1;
  else
    return ans;
}

Compilation message

race.cpp:85:37: error: declaration of 'H' as multidimensional array must have bounds for all dimensions except the first
 int best_path(int n, int k, int H[][], int L[]){
                                     ^
race.cpp:85:38: error: expected ')' before ',' token
 int best_path(int n, int k, int H[][], int L[]){
                                      ^
race.cpp:85:40: error: expected unqualified-id before 'int'
 int best_path(int n, int k, int H[][], int L[]){
                                        ^~~