| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 246934 |
2020-07-10T15:22:50 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;
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[find(y)]+=sz[find(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
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++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3456 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
3456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
