Submission #876255

#	Time	Username	Problem	Language	Result	Execution time	Memory
876255		hyakup	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 3e5 + 10;
const int maxk = 1e6 + 10;
vector<pair< int, ll>> adj[maxn];
vector<int> removed( maxn ), sub( maxn ), melhor( maxk, maxk );
int N, K;
int resp = maxk;

void dfsInit( int cur, int pai ){
     sub[cur] = 1;
     for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
          dfsInit( viz, cur );
          sub[cur] += sub[viz];
     }
}

int findCentroid( int cur, int pai, int tam ){
     for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
          if( sub[viz] > tam/2 ) return findCentroid(viz, cur, tam);
     }
     return cur;
}

void dfs( int cur, int pai, int nivel, int dist, int t ){
     if( dist > K ) return;
     if( t == 1 ) resp = min( resp, nivel + melhor[K - dist] );
     if( t == 2 ) melhor[dist] = min( melhor[dist], nivel );
     if( t == 3 ) melhor[dist] = maxk;

     for( auto [viz, d] : adj[cur] ) if( viz != pai && !removed[viz] ){
          dfs( viz, cur, nivel + 1, dist + d, t );
     }
}

void decompose( int node ){
     dfsInit( node, node );
     int centroid = findCentroid( node, node, sub[node] );
     bug(centroid)
     melhor[0] = 0;
     for( auto [viz, d] : adj[centroid] ) if( !removed[viz] ){
          dfs( viz, centroid, 1, d, 1 );
          dfs( viz, centroid, 1, d, 2 );
     }
     dfs( centroid, centroid, 0, 0, 3 );

     removed[centroid] = 1;

     for( auto[ viz, d ] : adj[centroid] ) if( !removed[viz] ) decompose( viz );
}

int best_path( int n, int k, int h[][2], int l[] ){
     N = n, K = k;
     for( int i = 0; i < n - 1; i++ ){
          adj[h[i][0]].push_back({ h[i][1], l[i] });
          adj[h[i][1]].push_back({ h[i][0], l[i] });
     }
     decompose(0);
     if( resp == maxk ) resp = -1;
     return resp;
}

int main(){
     int n, k; cin >> n >> k;
     N = n; K = k;
     for( int i = 1; i < n; i++ ){
          int a, b, c; cin >> a >> b >> c;
          adj[a].push_back({ b, c });
          adj[b].push_back({ a, c });
     }
     decompose(0);
     if( resp == maxk ) resp = -1;
     cout << resp << endl;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccQ2RrfU.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLWweFT.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status