Submission #246905

#	Time	Username	Problem	Language	Result	Execution time	Memory
246905		vanic	Toll (APIO13_toll)	C++14	16 / 100	8 ms	3456 KiB

toll

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <string.h>
#include <array>
#include <bitset>

using namespace std;

typedef long long ll;
const int maxn=1e5+5;

vector < pair < int, pair < int, int > > > svi;
vector < pair < int, pair < int, bool > > > ms[maxn];
vector < pair < int, int > > spec;
int br[maxn];
ll sol;

struct union_find{
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		if(sz[find(x)]>sz[find(y)]){
			swap(x, y);
		}
		parent[find(x)]=parent[find(y)];
		sz[y]+=sz[x];
		
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};

union_find U;

int dfs(int x, int prosl, int val, bool p){
	int broj=br[x];
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i].first!=prosl){
			broj+=dfs(ms[x][i].first, x, ms[x][i].second.first, ms[x][i].second.second);
		}
	}
	if(p){
		sol+=(ll)broj*val;
	}
	return broj;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	int a, b, c;
	for(int i=0; i<m; i++){
		cin >> a >> b >> c;
		a--;
		b--;
		svi.push_back({c, {a, b}});
	}
	sort(svi.begin(), svi.end());
	for(int i=0; i<k; i++){
		cin >> a >> b;
		a--;
		b--;
		spec.push_back({a, b});
	}
	for(int i=0; i<n; i++){
		cin >> br[i];
	}
	bool p;
	for(int i=0; i<m; i++){
		if(!U.query(svi[i].second.first, svi[i].second.second)){
			U.update(svi[i].second.first, svi[i].second.second);
			p=1;
			for(int j=0; j<spec.size(); j++){
				if(U.query(spec[j].first, spec[j].second)){
					if(p){
						ms[spec[j].first].push_back({spec[j].second, {svi[i].first, 1}});
						ms[spec[j].second].push_back({spec[j].first, {svi[i].first, 1}});
						p=0;
					}
					spec.erase(spec.begin()+j);
					j--;
				}
			}
			if(p){
				ms[svi[i].second.first].push_back({svi[i].second.second, {svi[i].first, 0}});
				ms[svi[i].second.second].push_back({svi[i].second.first, {svi[i].first, 0}});
			}
		}
	}
	dfs(1, 1, 0, 0);
	cout << sol << '\n';
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int dfs(int, int, int, bool)':
toll.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<spec.size(); j++){
                 ~^~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22