CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:Salama
Submission time:2021-10-17 17:11:11
Language:C++17
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2--2, 3details
#3--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < n-1; i++) {
                 ~~^~~~~
input/code.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < n-1; i++) {
                 ~~^~~~~

Code

#include <bits/stdc++.h>
using namespace std;

unsigned long long tc = 0;
//  src kone		dst kone			spd
map<unsigned, map<unsigned long long, unsigned long long>> v;
//	dpt		src kone			spd
map<unsigned, map<unsigned, unsigned long long>> h;
map<unsigned, unsigned long long>::iterator i;


void haku(int s, unsigned long long e, int d) {
	for (auto u : v[s]) {
		if(u.first == e) continue;
		if(h.count(d) && d > 0) {
			i = h[d].begin();
			for(; i != h[d].end(); i++) {
				h[d+1][i->first] = min(i->second, v[s][u.first]);
			}
		}
		haku(u.first, s, d+1);
		i = h[d+1].begin();
		for(; i != h[d+1].end(); i++) {
			h[d][i->first] = max(h[d][i->first], i->second);
		}
	}
	//h[d] = h[d+1];
	//h.erase(d+1);
	h[d][s] = v[e][s];
	h[d-1][s] = v[e][s];
	i = h[d].begin();
	for(;i != h[d].end(); i++) {
		h[d][i->first] = min(i->second, h[d][s]);
		//cout << s+1 << ": " << min(i->second, h[d][s]) << "@" << d << "\n";
	}
	tc = accumulate(h[d].begin(), h[d].end(), tc, [&d, &s](const size_t p, const auto& e){return p + min(e.second, h[d][s]);});
	//cout << tc << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	unsigned long long a, b;
	unsigned long long x, n;
	cin >> n;
	for(int i = 0; i < n-1; i++) {
		cin >> a >> b >> x;
		v[a-1][b-1] = x;
		v[b-1][a-1] = x;
	}
	unsigned s = 0;
	for(int i = 0; i < n-1; i++) {
		if(v[i].size() == 1) {
			s = i;
			break;
		}
	}

	haku(s, -1, 0);
	cout << tc << "\n";
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
(empty)

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)