| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 523854 |
2022-02-08T09:34:24 Z |
pokmui9909 |
Toll (APIO13_toll) |
C++17 |
|
4 ms |
3484 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);
}
vector<ll> p;
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[a] += p[b];
p[b] = a;
}
bool Same(ll a, ll b){ return Find(a) == Find(b); }
private:
};
ll N, M, K;
struct Edge{
ll u, v, c;
bool operator<(const Edge &r)const{
return c < r.c;
}
};
vector<Edge> E;
vector<Edge> add;
ll P[100005];
UnionFind S(100005);
vector<pair<ll, ll>> G[100005];
ll Par[35];
ll depth[35];
ll MinCost[35];
ll cnt[35];
vector<Edge> rem;
vector<pair<ll, ll>> CG[35];
vector<Edge> NE;
vector<Edge> X;
ll NP[35];
ll num[100005];
ll check[30][30];
void dfs1(ll n, ll p){
Par[n] = p;
cnt[n] = NP[n];
for(auto i : CG[n]){
ll nx = i.x, c = i.y;
if(nx == p) continue;
depth[nx] = depth[n] + 1;
dfs1(i.x, n);
cnt[n] += cnt[nx];
}
}
ll sum = 0, Comps = 0;
void dfs3(ll n){
num[n] = Comps;
NP[Comps] += P[n];
for(auto j : G[n]){
if(num[j.x]) continue;
dfs3(j.x);
}
}
void init(){
for(int i = 0; i < 25; i++){
for(int j = 0; j < 25; j++){
check[i][j] = 1e10;
}
}
vector<Edge> MST;
for(int i = 0; i < K; i++){
ll u = add[i].u, v = add[i].v;
S.Union(u, v);
}
for(int i = 0; i < M; i++){
ll u = E[i].u, v = E[i].v, c = E[i].c;
if(S.Same(u, v)) continue;
MST.push_back(E[i]);
}
for(int i = 0; i < MST.size(); i++){
ll u = MST[i].u, v = MST[i].v, c = MST[i].c;
if(S.Same(u, v)){
rem.push_back({u, v, c});
} else {
G[u].push_back({v, c});
G[v].push_back({u, c});
S.Union(u, v);
}
}
for(int i = 1; i <= N; i++){
if(num[i]) continue;
Comps++;
dfs3(i);
}
for(int i = 0; i < rem.size(); i++){
ll u = rem[i].u, v = rem[i].v, c = rem[i].c;
u = num[u], v = num[v];
if(u == v) continue;
if(u > v) swap(u, v);
check[u][v] = min(check[u][v], c);
}
for(int i = 1; i <= Comps; i++){
for(int j = i + 1; j <= Comps; j++){
if(check[i][j] >= 1e10) continue;
NE.push_back({i, j, check[i][j]});
}
}
assert(NE.size() <= 130);
sort(NE.begin(), NE.end());
for(int i = 0; i < K; i++){
add[i].u = num[add[i].u];
add[i].v = num[add[i].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;
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];
}
sort(E.begin(), E.end());
init();
ll ans = 0;
for(int bit = 0; bit < (1 << K); bit++){
for(int i = 0; i < 25; i++){
CG[i].clear();
MinCost[i] = 1e10;
S.p[i] = -1;
}
X.clear();
ll ok = 1;
for(int i = 0; i < K; i++){
if(bit == -1 || bit & (1 << i)){
ll u = add[i].u, v = add[i].v;
if(S.Same(u, v)){
ok = 0;
break;
}
S.Union(u, v);
CG[u].push_back({v, -1});
CG[v].push_back({u, -1});
}
}
if(!ok) continue;
for(int i = 0; i < NE.size(); i++){
ll u = NE[i].u, v = NE[i].v, c = NE[i].c;
if(S.Same(u, v)){
X.push_back({u, v, c});
continue;
}
S.Union(u, v);
CG[u].push_back({v, c});
CG[v].push_back({u, c});
}
dfs1(1, -1);
for(int i = 0; i < X.size(); i++){
ll u = X[i].u, v = X[i].v, c = X[i].c;
if(depth[u] < depth[v]) swap(u, v);
while(depth[u] > depth[v]){
MinCost[u] = min(MinCost[u], c);
u = Par[u];
}
while(u != v){
MinCost[u] = min(MinCost[u], c);
MinCost[v] = min(MinCost[v], c);
u = Par[u];
v = Par[v];
}
}
sum = 0;
for(int i = 0; i < K; i++){
if(bit & (1 << i)){
ll u = add[i].u, v = add[i].v;
if(depth[u] > depth[v]) swap(u, v);
sum += MinCost[v] * cnt[v];
}
}
ans = max(ans, sum);
}
cout << ans;
}
Compilation message
toll.cpp: In function 'void dfs1(ll, ll)':
toll.cpp:53:22: warning: unused variable 'c' [-Wunused-variable]
53 | ll nx = i.x, c = i.y;
| ^
toll.cpp: In function 'void init()':
toll.cpp:82:36: warning: unused variable 'c' [-Wunused-variable]
82 | ll u = E[i].u, v = E[i].v, c = E[i].c;
| ^
toll.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < MST.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i = 0; i < rem.size(); i++){
| ~~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:161:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int i = 0; i < NE.size(); i++){
| ~~^~~~~~~~~~~
toll.cpp:172:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int i = 0; i < X.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
3484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
3484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
3484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
3484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
