oj.uz

답안 #876256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876256 2023-11-21T13:19:02 Z hyakup 경주 (Race) (IOI11_race) C++17
0 / 100
 5 ms 17244 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -