CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:okkokko
Submission time:2021-10-14 18:51:25 +0300
Language:C++11
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#20.02 s2, 3details
#30.53 s3details

Code

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


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

map<int,int> Crossroads(int kone,int source,int sourceSpeed) {
	tries+=1;
	//if (tries>300){cout << "x";return yhteydet;}
	
	map<int,int> &ko = koneet[kone];
	int haaSize = ko.size()-1;
	
	if(haaSize==0){
	
		//return map<int,int> {{sourceSpeed,1}};
		map<int,int> a;
		a[sourceSpeed]=1;
		return a;
	}
	
	if (source==0){
		haaSize+=1;
	}
	
	vector<map<int,int>> haarat(haaSize+1);  //=new map<int,int>[haaSize+1];
	int 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<int,int> yhteydet;
	yhteydet[sourceSpeed] = 1;
	
	//for (int i = 0; i<haaSize; i++){
	for (auto &item1 : haarat){
		for (auto &item : item1){
			int 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<int,int> yhtyhaara;
		
		//for (int i = 0; i<haaSize; i++){
		for (auto &item1 : haarat){
			for (auto &item : item1){
				yhtyhaara.emplace(item.first,0);
				yhtyhaara[item.first]+=item.second;
			}
		}
		//int yhSize = yhtyhaara.size();

		int ta = 0;
		int 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){
			int ta = 0;
			int 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(){
	int n;
	cin >> n;
	koneet =new map<int,int>[n+1];
	for (int i = 0; i<n; i++){
		int 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:

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

correct output
1103702320243776

user output
3683886326848

Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
147880143772979