CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:Kertor
Submission time:2021-10-13 02:10:40
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.03 s2, 3details
#30.78 s3details

Code

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <string>
#include <sstream>
#include <bits/stdc++.h>
#define lint long long int

using namespace std;

struct computer 
{
	int backwardConnection;
	vector<int> history;
};

int commonComputer(vector<int> first_history, vector<int> second_history) {
	int i = 0;
	while(first_history[i] == second_history[i]) {
		i++;
	}
	return i;
}

int main()
{
    int n; cin >> n;
    computer network[n];
    network[0].history.push_back(1);
    network[0].backwardConnection = 0;
    for(int i = 0; i < n - 1; i++) 
    {
    	int idf; cin >> idf;
    	int ids; cin >> ids;
    	int speed; cin >> speed;
    	network[ids-1].backwardConnection = speed;
    	network[ids-1].history = vector<int>(network[idf-1].history);
    	network[ids-1].history.push_back(ids);
	}
	
	int sum = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1 + i; j <= n; j++) {
			int commonPC = commonComputer(network[i-1].history, network[j-1].history);
			int currMin = network[j-1].backwardConnection;
			vector<int> currentHistory = network[i-1].history;
			int currID = i;
			cout << "Hello" << endl;
			while(currID != commonPC) {
				currMin = min(currMin, network[currentHistory.back() - 1].backwardConnection);
				currentHistory.pop_back();
				currID = currentHistory.back();
			}
			currentHistory.clear();
			currentHistory = network[j-1].history;
			currID = j;
			while(currID != commonPC) {
				currMin = min(currMin, network[currentHistory.back() - 1].backwardConnection);
				currentHistory.pop_back();
				currID = currentHistory.back();
			}
			sum += currMin;
		}
	} 
	cout << sum;
	return 0;
}



Test details

Test 1

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
Hello
Hello
Hello
Hello
Hello
...

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
Hello
Hello
Hello
Hello
Hello
...

Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
Hello
Hello
Hello
Hello
Hello
...