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
AC × 4
AC × 19
WA × 7
AC × 36
WA × 16
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