| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6054 |
2014-06-15T21:44:59 Z |
kriii |
오두막집 (GA7_cabana) |
C++ |
|
28 ms |
6520 KB |
#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];
int q[100001],z[100001],d[100001];
pair<vector<int>, long long> over(int s, int dist)
{
int n = 0, h = 0;
q[h] = s; d[h] = 0; h++; chk[s] = s;
while (n < h){
int u = q[n], w = d[n]; n++;
for (int t=0,i;t<g[u].size();t++) if (!fb[i=g[u][t]]){
int v = (u == x[i]) ? y[i] : x[i];
if (chk[v] != s){
q[h] = v; d[h] = (w+c[i]); h++; chk[v] = s;
}
}
}
int dif = 2*n; int st = q[0];
for (int i=n-1;i>=0;i--){
int u = q[i]; z[i] = 1;
int mx = 0;
for (int t=0,j;t<g[u].size();t++) if (!fb[j=g[u][t]]){
int v = (u == x[j]) ? y[j] : x[j];
if (chk[v] != s){
z[i] += z[-chk[v]];
mx = max(mx,z[-chk[v]]);
}
}
mx = max(mx,n-z[i]);
if (dif > mx) st = u, dif = mx;
chk[u] = -i;
}
pair<vector<int>, long long> ret;
for (int i=0;i<n;i++) if (ca[q[i]]) ret.first.push_back(d[i]);
sort(ret.first.begin(),ret.first.end());
ret.second = 0;
vector<pair<vector<int>, long long> > a; vector<int> ad;
for (int t=0,i;t<g[st].size();t++) if (!fb[i=g[st][t]]) fb[i] = 1, ad.push_back(i);
for (int t=0;t<ad.size();t++) a.push_back(over(st==x[ad[t]]?y[ad[t]]:x[ad[t]],dist));
for (int t=0;t<a.size();t++){
int o = c[ad[t]];
for (int r=0;r<a[t].first.size();r++){
a[t].first[r] += o;
if (ca[st] && a[t].first[r] <= dist) ret.second++;
}
}
while (a.size() > 1){
vector<pair<vector<int>, long long> > b;
for (int k=0;k<a.size();k+=2){
if (k + 1 == a.size()){b.push_back(a[k]); continue;}
pair<vector<int>, long long> e;
e.second = a[k].second + a[k+1].second;
for (int i=0,j=(int)a[k+1].first.size()-1;i<a[k].first.size();i++){
while (j >= 0 && a[k].first[i] + a[k+1].first[j] > dist) j--;
e.second += j + 1;
}
int i=0,j=0;
while (i<a[k].first.size() && j<a[k+1].first.size()){
if (a[k].first[i] < a[k+1].first[j])
e.first.push_back(a[k].first[i++]);
else
e.first.push_back(a[k+1].first[j++]);
}
while (i<a[k].first.size()) e.first.push_back(a[k].first[i++]);
while (j<a[k+1].first.size()) e.first.push_back(a[k+1].first[j++]);
b.push_back(e);
}
a.clear(); a = b; b.clear();
}
if (!a.empty()) ret.second = a[0].second;
for (int t=0;t<ad.size();t++) fb[ad[t]] = 0;
return ret;
}
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 = -1;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
6520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
