Submission #245921

#	Time	Username	Problem	Language	Result	Execution time	Memory
245921		oscarsierra12	Race (IOI11_race)	C++14	0 / 100	11 ms	7424 KiB

race

#include "race.h"
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>

using namespace std ;

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

const int MAX_N = 3e5+2 ;

typedef pair<int,int>   ii ;

vector <ii> G[MAX_N];
int depth[MAX_N];
int sz[MAX_N] ;
int ans = 1e9+7 ;
int k ;
int visit[MAX_N];

void calc ( int u, int p, int d ) {
    depth[u] = d ;
    sz[u] = 1;
    for ( auto v:G[u] ) {
        if ( visit[v.ff] || v.ff == p) continue ;
        calc ( v.ff, u, d+1 ) ;
        sz[u] += sz[v.ff] ;
    }
}

int centroid ( int u, int p, int el ) {
    int ok = 1, x = -1 ;
    for ( auto v:G[u] ) {
        if ( visit[v.ff] ) continue ;
        if ( v.ff!=p ) {
            cout << el/2 << ' ' << v.ff << ' ' << sz[v.ff] << endl ;
            ok &= (sz[v.ff] <= el/2) ;
            x = max ( x, centroid(v.ff, u, el) ) ;
        }
    }
    if ( ok && (el-sz[u]) <= el/2 ) x = max (x, u) ;
    return x ;
}

map <int, int> mp ;
vector <ii> car ;

void doit ( int u, int p, int val ) {
    if ( mp[k-val] != 0 ) ans = min ( ans, mp[k-val] + depth[u] - 2 ) ;
    car.push_back ({val, depth[u]}) ;
    for ( auto v:G[u] ) {
        if ( v.ff==p || visit[v.ff] ) continue ;
        doit ( v.ff, u, min ( 1000010, val + v.ss ) ) ;
    }
}

int go ( int u ) {
    calc ( u, -1, 1 ) ;
    int root = centroid ( u, -1, sz[u] ) ;
    cout << "centroid = " << root << endl ;
    calc ( root, -1, 1 ) ;
    mp[0] = 1 ;
    for ( auto v:G[root] ) {
        if ( visit[v.ff] ) continue ;
        doit ( v.ff, root, v.ss ) ;
        for ( auto i:car ) {
            if ( mp[i.ff] == 0 ) mp[i.ff] = i.ss ;
            mp[i.ff] = min ( mp[i.ff], i.ss ) ;
        }
        car.clear() ;
    }
    mp.clear() ;
    visit[root] = 1 ;
    for ( auto v:G[root] ) {
        if ( visit[v.ff] ) continue ;
        go ( v.ff ) ;
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K ;
  for ( int i = 0 ; i+1 < N ;++i ) {
    G[H[i][0]].push_back ( {H[i][1], L[i]} ) ;
    G[H[i][1]].push_back ( {H[i][0], L[i]} ) ;
  }
  go ( 0 ) ;
  if ( ans > MAX_N ) ans = -1 ;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'int go(int)':
race.cpp:96:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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