| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20880 |
2017-03-03T06:00:51 Z |
kdh9949 |
오두막집 (GA7_cabana) |
C++14 |
|
16 ms |
7884 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct E{ int x, c; };
int n, m, chk[100010], s[100010], vis[100010];
vector<E> e[100010];
vector<int> av, cv[100010];
ll K;
int sd(int x, int p){
if(vis[x]) return 0;
s[x] = 1;
for(auto &i : e[x]) if(i.x != p) s[x] += sd(i.x, x);
return s[x];
}
int cd(int x, int p, int n){
for(auto &i : e[x]){
if(vis[i.x] || i.x == p) continue;
if(s[i.x] > n / 2) return cd(i.x, x, n);
}
return x;
}
void dd(vector<int> &v, int x, int p, int d, int k){
if(vis[x] || d > k) return;
if(chk[x]) v.push_back(d);
for(auto &i : e[x]) if(i.x != p) dd(v, i.x, x, d + i.c, k);
}
ll f(int x, int k){
sd(x, 0);
x = cd(x, 0, s[x]);
for(int i = 0; i < e[x].size(); i++){
dd(cv[i], e[x][i].x, x, e[x][i].c, k);
for(auto &j : cv[i]) av.push_back(j);
sort(cv[i].begin(), cv[i].end());
}
sort(av.begin(), av.end());
ll ret = 0;
for(int i = 0; i < e[x].size(); i++){
for(auto &j : cv[i]){
ret += (int)(upper_bound(av.begin(), av.end(), k - j) - av.begin()) -
(int)(upper_bound(cv[i].begin(), cv[i].end(), k - j) - cv[i].begin());
}
vector<int>().swap(cv[i]);
}
vector<int>().swap(av);
ret /= 2; ret += chk[x] * (int)av.size();
vis[x] = 1;
for(auto &i : e[x]){
if(ret >= K) return K;
if(!vis[i.x]) ret += f(i.x, k);
}
return ret;
}
int can(int k){ fill(vis + 1, vis + n + 1, 0); return f(1, k) >= K; }
int main(){
scanf("%d%d%lld", &n, &m, &K);
for(int i = 2, x, y; i <= n; i++){
scanf("%d%d", &x, &y);
e[i].push_back({x, y});
e[x].push_back({i, y});
}
for(int i = 0, x; i < m; i++){
scanf("%d", &x);
chk[x] = 1;
}
int s = 1, e = 3e7;
for(int m; s <= e; ){
m = (s + e) / 2;
if(can(m)) e = m - 1;
else s = m + 1;
}
printf("%d\n", s);
}
Compilation message
cabana.cpp: In function 'll f(int, int)':
cabana.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < e[x].size(); i++){
^
cabana.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < e[x].size(); i++){
^
cabana.cpp: In function 'int main()':
cabana.cpp:63:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &n, &m, &K);
^
cabana.cpp:65:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^
cabana.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
7884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
7884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
