Submission #876256

#	Time	Username	Problem	Language	Result	Execution time	Memory
876256		hyakup	Race (IOI11_race)	C++17	0 / 100	5 ms	17244 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;
}

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