| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1197298 | nub | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define ps push
#define pp pop
using namespace std;
string file_name = "";
string input_extension = "";
string output_extension = "";
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(rng);
}
ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;
cll MOD = 1e18;
ll mulmod(ll a, ll b){
return (a%MOD)*(b%MOD)%MOD;
}
ll binpow(ll a, ll b){
if (b == 0) return 1;
if (b == 1) return a%MOD;
if (b%2 == 0) return binpow(mulmod(a, a), b/2);
else return mulmod(a, binpow(mulmod(a, a), b/2));
}
ll invmod(ll a){
return binpow(a, MOD-2);
}
ci N = 2e5+1;
vector<vector<pair<int, int>>> adj;
map<int, int> mp[N];
int n, k, res = inf;
void dfs(int cur, int par){
mp[cur][0] = 0;
int p, w;
int len, dis;
for (pair<int, int> temp : adj[cur]){
p = temp.fi; w = temp.se;
if (p == par) continue;
dfs(p, cur);
for (pair<int, int> i : mp[p]){
len = i.fi + w;
dis = i.se + 1;
if (len > 1e6) continue;
if (mp[cur].count(k-len) > 0){
res = min(res, dis + mp[cur][k-len]);
}
}
for (pair<int, int> i : mp[p]){
len = i.fi + w;
dis = i.se + 1;
if (mp[cur].count(len) == 0) mp[cur][len] = dis;
else mp[cur][len] = min(mp[cur][len], dis);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
adj.resize(n);
int s, e, w;
for (int i=0; i<n-1; i++){
s = H[i][0];
e = H[i][1];
w = L[i];
adj[s].psb({e, w});
adj[e].psb({s, w});
}
dfs(0, -1);
if (res == inf) return -1;
else return res;
}
int main(){
}