CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:okkokko
Submission time:2021-10-14 19:37:55
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.02 s2, 3details
#3ACCEPTED0.53 s3details

Code

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


map<long,long> *koneet;
long total = 0;
long tries = 0;

map<long,long> Crossroads(long kone,long source,long sourceSpeed) {
	tries+=1;
	//if (tries>300){cout << "x";return yhteydet;}
	
	map<long,long> &ko = koneet[kone];
	long haaSize = ko.size()-1;
	
	if(haaSize==0){
	
		//return map<long,long> {{sourceSpeed,1}};
		map<long,long> a;
		a[sourceSpeed]=1;
		return a;
	}
	
	if (source==0){
		haaSize+=1;
	}
	
	vector<map<long,long>> haarat(haaSize+1);  //=new map<long,long>[haaSize+1];
	long i_k = 0;
	for (auto &item : ko){
		if (item.first !=source){
			haarat[i_k]=Crossroads(item.first,kone,item.second);
			//delete koneet[item.first];
			i_k+=1;
		}
	}
	long addTotalHalf = 0;
	map<long,long> yhteydet;
	yhteydet[sourceSpeed] = 1;
	
	//for (long i = 0; i<haaSize; i++){
	for (auto &item1 : haarat){
		for (auto &item : item1){
			long a = std::min(item.first, sourceSpeed);
			yhteydet.emplace(a,0);
			yhteydet[a]+=item.second;
			addTotalHalf+=2*item.second*item.first;
		}
	}
	
	if (haaSize>1){
		//long addTotalHalf = 0;
		map<long,long> yhtyhaara;
		
		//for (long i = 0; i<haaSize; i++){
		for (auto &item1 : haarat){
			for (auto &item : item1){
				yhtyhaara.emplace(item.first,0);
				yhtyhaara[item.first]+=item.second;
			}
		}
		//long yhSize = yhtyhaara.size();

		long ta = 0;
		long tb = 0;
		for (auto &item : yhtyhaara){
			tb+=item.second;
		}
		for (auto &item : yhtyhaara){
			ta+=item.first*item.second;
			tb-=item.second;
			addTotalHalf+=(ta+tb*item.first)*item.second;
		}
		for (auto &item1 : haarat){
			long ta = 0;
			long tb = 0;
			for (auto &item : item1){
				tb+=item.second;
			}
			for (auto &item : item1){
				ta+=item.first*item.second;
				tb-=item.second;
				addTotalHalf-=(ta+tb*item.first)*item.second;
			}
		}
		//addTotal+=addTotalHalf/2;
		}
	
	total+=addTotalHalf;
	//delete[] haarat;
	return yhteydet;
}

int main(){
	long n;
	cin >> n;
	koneet =new map<long,long>[n+1];
	for (long i = 0; i<n; i++){
		long c0,c1,c2;
		cin >> c0 >> c1 >> c2;
		koneet[c0][c1]=c2;
		koneet[c1][c0]=c2;
	}

	Crossroads(1,0,0);
	cout << total/2;

    return 0;
}

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: ACCEPTED

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

correct output
1103702320243776

user output
1103702320243776

Test 3

Group: 3

Verdict: ACCEPTED

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

correct output
1080549209850010931

user output
1080549209850010931