제출 #246921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246921		vanic	통행료 (APIO13_toll)	C++14	0 / 100	6 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;

set < pair < int, pair < int, int  > > > svi;
vector < pair < int, int > > ms1[maxn];
pair < int, int > 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){
	if(x==0){
		return 0;
	}
	return ms[x].second+dfs(ms[x].first);
}

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--;
		ms1[a].push_back({c, b});
		ms1[b].push_back({c, a});
	}
	for(int i=0; i<ms1[0].size(); i++){
		svi.insert({ms1[0][i].first, {0, ms1[0][i].second}});
	}
	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;
	pair < int, pair < int, int > > x;
	vector < int > skup;
	int maksi, ind, val;
	while(!svi.empty()){
		x=*svi.begin();
		svi.erase(svi.begin());
		if(!U.query(x.second.first, x.second.second)){
			p=1;
			U.update(x.second.first, x.second.second);
			for(int i=0; i<ms1[x.second.second].size(); i++){
				svi.insert({ms1[x.second.second][i].first, {x.second.second, ms1[x.second.second][i].second}});
			}
			for(int i=0; i<spec.size(); i++){
				if(U.query(spec[i].first, spec[i].second)){
					p=0;
					if(spec[i].first==x.second.second){
						skup.push_back(spec[i].second);
					}
					else{
						skup.push_back(spec[i].first);
					}
					spec.erase(spec.begin()+i);
					i--;
				}
			}
			if(p){
				sol+=(ll)dfs(x.second.first)*br[x.second.second];
				ms[x.second.second]={x.second.first, 0};
			}
			else{
//				cout << "Usao" << endl;
				sol+=(ll)x.first*br[x.second.second];
				maksi=-1;
				for(int i=0; i<skup.size(); i++){
					val=dfs(skup[i]);
					if(val>maksi){
						maksi=val;
						ind=i;
					}
				}
				ms[x.second.second]={skup[ind], x.first};
				sol+=(ll)val*br[x.second.second];
				skup.clear();
			}
		}
	}
	cout << sol << '\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int main()':
toll.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms1[0].size(); i++){
               ~^~~~~~~~~~~~~~
toll.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<ms1[x.second.second].size(); i++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<spec.size(); i++){
                 ~^~~~~~~~~~~~
toll.cpp:123:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<skup.size(); i++){
                  ~^~~~~~~~~~~~
toll.cpp:131:10: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
     sol+=(ll)val*br[x.second.second];
          ^~~~~~~
toll.cpp:130:34: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ms[x.second.second]={skup[ind], x.first};
                                  ^

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