| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 6044 | kriii | 오두막집 (GA7_cabana) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int N,M; long long K;
int x[100001],y[100001],c[100001],chk[100001]; bool fb[100001],ca[100001];
vector<int> g[100001];
pair<vector<int>, long long> over(int s, int dist)
{
vector<int> q,z,d; int n = 0;
q.push_back(s); d.push_back(0); chk[s] = s;
while (n < q.size()){
int u = q[n], w = d[n]; n++;
for (int i : g[u]) if (!fb[i]){
int v = (u == x[i]) ? y[i] : x[i];
if (chk[v] != s){
q.push_back(v); d.push_back(w+c[i]); chk[v] = s;
}
}
}
z.resize(n); long long opp = 0; int cut = -1;
for (int i=n-1;i>=0;i--){
int u = q[i]; z[i] = 1;
for (int j : g[u]) if (!fb[j]){
int v = (u == x[j]) ? y[j] : x[j];
if (chk[v] != s){
z[i] += z[-chk[v]];
if (opp < (long long) n * (n - z[-chk[v]])){
opp = (long long) n * (n - z[-chk[v]]);
cut = j;
}
}
}
chk[u] = -i;
}
long long cnt = 0;
if (cut != -1){
fb[cut] = 1;
pair<vector<int>, long long> a = over(x[cut],dist);
pair<vector<int>, long long> b = over(y[cut],dist);
cnt = a.second + b.second;
for (int i=0,j=(int)b.first.size()-1;i<a.first.size();i++){
while (j >= 0 && a.first[i] + c[cut] + b.first[j] > dist) j--;
cnt += j + 1;
}
fb[cut] = 0;
}
vector<int> ret;
for (int i=0;i<n;i++) if (ca[q[i]]) ret.push_back(d[i]);
sort(ret.begin(),ret.end());
return make_pair(ret,cnt);
}
int main()
{
scanf ("%d %d %lld",&N,&M,&K);
for (int i=2;i<=N;i++){
scanf ("%d %d",&y[i],&c[i]); x[i] = i;
g[x[i]].push_back(i);
g[y[i]].push_back(i);
}
while (M--){
int v; scanf ("%d",&v);
ca[v] = 1;
}
int l = 1, r = 250 * N, m, a;
while (l <= r){
m = (l + r) / 2;
if (over(1,m).second >= K){
r = m - 1;
a = m;
}
else l = m + 1;
}
printf ("%d\n",a);
return 0;
}