| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 506567 |
2022-01-12T05:42:19 Z |
pokmui9909 |
Toll (APIO13_toll) |
C++14 |
|
3 ms |
6476 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];
ll depth[100005];
struct MyStruct{
ll n, c, f;
};
vector<vector<MyStruct>> G(100005);
ll sum = 0, ans = 0;
ll MinCost[100005];
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];
}
}
void init(){
fill(depth, depth + 100005, -1);
fill(MinCost, MinCost + 100005, 1e18);
queue<ll> Q;
depth[1] = 0;
Q.push(1);
while(!Q.empty()){
ll u = Q.front(); Q.pop();
for(auto v : T[u]){
if(depth[v.x] != -1) continue;
depth[v.x] = depth[u] + 1;
Q.push(v.x);
}
}
for(int i = 0; i < M; i++){
if(depth[E[i].u] > depth[E[i].v]){
swap(E[i].u, E[i].v);
}
}
for(int i = 0; i < K; i++){
if(depth[add[i].x] > depth[add[i].y]){
swap(add[i].x, add[i].y);
}
}
MinCost[1] = 0;
for(int i = 1; i <= N; i++){
//cout << "depth " << i << ' ' << depth[i] << '\n';
for(auto j : T[i]){
if(depth[i] <= depth[j.x]) continue;
MinCost[i] = min(MinCost[i], j.y);
}
//cout << ">> " << i << ' ' << MinCost[i] << '\n';
}
}
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});
}
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];
}
init();
sort(E.begin(), E.end());
if(N == 1){
cout << 0;
return 0;
}
for(int i = 3; i < 4; 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, MinCost[v]});
}
}
}
if(!ok) continue;
vector<Edge> MST;
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});
}
}
for(int j = 0; j < V.size(); j++){
ll u = V[j].u, v = V[j].v, c = V[j].c;
G[u].push_back({v, c, 1});
G[v].push_back({u, c, 1});
//cout << u << ' ' << v << ' '<< c << '\n';
}
//cout << "\n\n\n";
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});
//cout << u << ' ' << v << ' '<< c << '\n';
}
sum = 0;
dfs(1, -1);
ans = max(ans, sum);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:142:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int j = 0; j < V.size(); j++){
| ~~^~~~~~~~~~
toll.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int j = 0; j < MST.size(); j++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
