| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246921 |
2020-07-10T14:41:11 Z |
vanic |
Toll (APIO13_toll) |
C++14 |
|
6 ms |
3456 KB |
#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;
}
Compilation message
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};
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
