| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 506447 |
2022-01-12T04:40:14 Z |
pokmui9909 |
Toll (APIO13_toll) |
C++14 |
|
2 ms |
4940 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define x first
#define y second
class UnionFind{
public:
UnionFind(ll S){
p.resize(S + 5, -1);
}
ll Find(ll n){
if (p[n] < 0) return n;
else return p[n] = Find(p[n]);
}
void Union(ll a, ll b){
a = Find(a), b = Find(b);
if (a == b) return;
p[b] += p[a];
p[a] = b;
}
bool Same(ll a, ll b) { return Find(a) == Find(b); }
private:
vector<ll> p;
};
ll N, M, K;
vector<vector<pair<ll, ll>>> T(100005);
struct Edge{
ll u, v, c;
bool operator<(const Edge &r)const{
return c < r.c;
}
};
vector<Edge> E;
vector<pair<ll, ll>> add;
ll P[100005];
ll Size[100005];
struct MyStruct{
ll n, c, f;
};
vector<vector<MyStruct>> G(100005);
ll sum = 0, ans = 0;
void dfs(ll u, ll p){
Size[u] = P[u];
for(auto i : G[u]){
ll v = i.n, c = i.c, f = i.f;
if(v == p) continue;
dfs(v, u);
Size[u] += Size[v];
sum += f * c * Size[v];
}
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> M >> K;
for(int i = 1; i <= M; i++){
ll u, v, c; cin >> u >> v >> c;
T[u].push_back({v, c});
T[v].push_back({u, c});
E.push_back({u, v, c});
}
sort(E.begin(), E.end());
for(int i = 1; i <= K; i++){
ll u, v; cin >> u >> v;
add.push_back({u, v});
}
for(int i = 1; i <= N; i++){
cin >> P[i];
}
for(int i = 0; i < (1 << K); i++){
for(int j = 1; j <= N; j++){
Size[j] = 0;
G[j].clear();
}
UnionFind uf(N);
ll ok = 1;
vector<Edge> V;
for(int j = 0; j < K; j++){
if(i & (1 << j)){
ll u = add[j].x, v = add[j].y;
if(uf.Same(u, v)){
ok = 0;
break;
} else {
uf.Union(u, v);
V.push_back({u, v, 0});
}
}
}
if(!ok) continue;
vector<Edge> MST;
ll MinCost = 1e18;
for(int j = 0; j < M; j++){
ll u = E[j].u, v = E[j].v, c = E[j].c;
if(!uf.Same(u, v)){
uf.Union(u, v);
MST.push_back({u, v, c});
} else {
MinCost = min(MinCost, c);
}
}
for(int j = 0; j < V.size(); j++){
ll u = V[j].u, v = V[j].v, c = MinCost;
G[u].push_back({v, c, 1});
G[v].push_back({u, c, 1});
}
for(int j = 0; j < MST.size(); j++){
ll u = MST[j].u, v = MST[j].v, c = MST[j].c;
G[u].push_back({v, c, 0});
G[v].push_back({u, c, 0});
}
sum = 0;
dfs(1, -1);
ans = max(ans, sum);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = 0; j < V.size(); j++){
| ~~^~~~~~~~~~
toll.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int j = 0; j < MST.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
