CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:shmoul
Submission time:2021-10-17 23:55:28 +0300
Language:C++17
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2--2, 3details
#3--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<Computers.size();i++)
              ~^~~~~~~~~~~~~~~~~
input/code.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=i+1;j<Computers.size();j++)
                 ~^~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <map>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")


using namespace std;


struct Connection
{
	int CompID;
	int Speed;
	Connection(int compid, int speed) {CompID=compid; Speed=speed;}
};
struct Computer
{
	list<Connection> Connections;
	Computer(){}
};

vector<Computer>	Computers;
long long			SpeedSum;
//map<long long, int> ConnectionCache;
map<pair<int ,int>, int> ConnectionCache;
int FindSpeed(int from, int to, int origin=-1)
{
	//auto x = ConnectionCache.find({from, to});
	//if(x!=ConnectionCache.end()) return x->second;
	Computer& c = Computers[from];
	int n=0;
	list<Connection> temp = c.Connections;
	for(Connection& conn : c.Connections)
	{
		if(origin==conn.CompID) continue;
		if(conn.CompID==to) return conn.Speed;
		int s = FindSpeed(conn.CompID, to, from);	
		/*if(ConnectionCache.find({from, to})!=ConnectionCache.end())
		{
			 if(n>ConnectionCache[{from, to}])
				ConnectionCache[{from, to}] = n;
		}
		else ConnectionCache[{from, to}] = n;*/
		if(s>0)
		{
			n=fmin(conn.Speed, s);
			break;
		}
	}
	return n;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int count;
	cin>>count;
	for(int i=0;i<=count;i++)
	{
		Computers.push_back(Computer());
	}
	for(int i=1;i<count;i++)
	{
		int compid1, compid2, speed;
		cin>>compid1>>compid2>>speed;
		Computer& comp1 = Computers[compid1];
		Computer& comp2 = Computers[compid2];
		comp1.Connections.push_back(Connection(compid2, speed));
		comp2.Connections.push_back(Connection(compid1, speed));
	}
	for(int i=1;i<Computers.size();i++)
	{
		for(int j=i+1;j<Computers.size();j++)
		{
			/*int Speed;
			auto x = ConnectionCache.find({j, i});
			auto y = ConnectionCache.find({i, j});
			if(x!=ConnectionCache.end()) SpeedSum += x->second;
			else if(y!=ConnectionCache.end()) SpeedSum += y->second;
			else Speed = FindSpeed(j, i);*/
			
			int Speed = FindSpeed(j, i);
			SpeedSum+=Speed;
		}
	}
	cout<<SpeedSum;
	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
(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)