Submission #1440973
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int n, k; vector<pii> lis[200100]; int dep[200100], md[200100]; void idfs(int here, int p, int d) { int i, t = -1; md[here] = dep[here] = d; for (i=0;i<lis[here].size();i++) { int there = lis[here][i].second; if (there==p) {t=i;continue;} idfs(there,here,d+lis[here][i].first); md[here] = max(md[there],md[here]); } if (~t) lis[here].erase(lis[here].begin()+t); sort(lis[here].begin(),lis[here].end(),[&](pii a, pii b){return md[a.second]>md[b.second];}); } int L, res; int dfs(int here, int c) { int mini = c; for (auto &tmp : lis[here]) { int there = tmp.second; int v = dfs(there,mini+tmp.first); mini = min(mini,v+tmp.first); } if (mini>=L) { mini = 0; res++; } return mini; } bool ok(int d) { L = d; res = 0; dfs(0,1e9+10); return res>=k; } int main() { int i; scanf("%d%d",&n,&k); for (i=0;i<n-1;i++) { int a, b, c; scanf("%d%d%d",&a,&b,&c); --a; --b; lis[a].push_back(pii(c,b)); lis[b].push_back(pii(c,a)); } idfs(0,-1,0); int s = 0, e = 1e9+2; while(s<=e) { int m = (s+e)>>1; if (ok(m)) s = m+1; else e = m-1; } printf("%d\n",e); return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - High-powered Illuminations |
User | tlwpdus |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1254 Byte |
Status | WA |
Exec Time | 321 ms |
Memory | 31488 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:47:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&k); ^ ./Main.cpp:50:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d",&a,&b,&c); --a; --b; ^
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 50 | 0 / 50 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
dataset1 | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt |
dataset2 | sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 3 ms | 4992 KB |
01-02.txt | AC | 51 ms | 6784 KB |
01-03.txt | AC | 51 ms | 6784 KB |
01-04.txt | AC | 51 ms | 6784 KB |
01-05.txt | WA | 52 ms | 6784 KB |
01-06.txt | AC | 52 ms | 6784 KB |
01-07.txt | WA | 46 ms | 6784 KB |
01-08.txt | WA | 48 ms | 6784 KB |
01-09.txt | WA | 47 ms | 6784 KB |
01-10.txt | WA | 45 ms | 7040 KB |
01-11.txt | WA | 45 ms | 7040 KB |
01-12.txt | WA | 45 ms | 7040 KB |
01-13.txt | AC | 29 ms | 6912 KB |
01-14.txt | AC | 23 ms | 6912 KB |
01-15.txt | AC | 23 ms | 6912 KB |
01-16.txt | AC | 23 ms | 6912 KB |
01-17.txt | AC | 46 ms | 10240 KB |
01-18.txt | AC | 45 ms | 10240 KB |
01-19.txt | AC | 23 ms | 6776 KB |
01-20.txt | AC | 23 ms | 6776 KB |
01-21.txt | AC | 23 ms | 6776 KB |
01-22.txt | AC | 29 ms | 6652 KB |
02-01.txt | AC | 287 ms | 13824 KB |
02-02.txt | AC | 287 ms | 13824 KB |
02-03.txt | WA | 289 ms | 13824 KB |
02-04.txt | WA | 305 ms | 13824 KB |
02-05.txt | WA | 290 ms | 13824 KB |
02-06.txt | AC | 290 ms | 13824 KB |
02-07.txt | AC | 253 ms | 13952 KB |
02-08.txt | WA | 252 ms | 13952 KB |
02-09.txt | WA | 258 ms | 13952 KB |
02-10.txt | WA | 258 ms | 13952 KB |
02-11.txt | WA | 255 ms | 15488 KB |
02-12.txt | WA | 262 ms | 15616 KB |
02-13.txt | WA | 255 ms | 15616 KB |
02-14.txt | AC | 119 ms | 14592 KB |
02-15.txt | AC | 119 ms | 14592 KB |
02-16.txt | AC | 119 ms | 14464 KB |
02-17.txt | AC | 321 ms | 31488 KB |
02-18.txt | AC | 305 ms | 31488 KB |
02-19.txt | AC | 125 ms | 14320 KB |
02-20.txt | AC | 112 ms | 14320 KB |
02-21.txt | AC | 207 ms | 13048 KB |
02-22.txt | AC | 305 ms | 31488 KB |
sample-01.txt | AC | 3 ms | 4992 KB |
sample-02.txt | AC | 3 ms | 4992 KB |
sample-03.txt | AC | 3 ms | 4992 KB |
sample-04.txt | AC | 2 ms | 4992 KB |