| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 552579 |
2022-04-23T11:05:31 Z |
QwertyPi |
Toll (APIO13_toll) |
C++14 |
|
2 ms |
2760 KB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
typedef uint32_t uint;
typedef pair<int, int> pii;
const int N = 1e5+1, K = 21;
vector<int> G[N];
vector<pii> H[K];
int A[N], w[K], sz[K];
unsigned ubits[1 << K], wei[1 << K][K];
struct edge{
int u, v, w;
bool operator< (const edge& o) const{
return w < o.w;
}
};
struct DSU{
int dsu[N], w[N];
void ini(int n, int* A = nullptr){
for(int i = 0; i <= n; i++) dsu[i] = i;
if(A != nullptr) for(int i = 0; i <= n; i++) w[i] = A[i];
}
int f(int x){
if(x == dsu[x]) return x;
return dsu[x] = f(dsu[x]);
}
bool join(int x, int y){
x = f(x), y = f(y);
if(x == y) return false;
dsu[x] = y;
w[y] += w[x];
return true;
}
bool join(edge e){
return join(e.u, e.v);
}
} dsu_r, dsu_t;
vector<edge> E, Q, tQ, tmp;
int dfs(int v, int weight = 0, int p = -1){
sz[v] = w[v];
int ret = 0;
for(auto i : H[v]){
if(i.fi != p){
ret += dfs(i.fi, i.se, v);
sz[v] += sz[i.fi];
}
}
ret += sz[v] * weight;
return ret;
}
int32_t main(){
int n, m, k, r;
cin >> n >> m >> k;
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
E.pb({u, v, w});
}
for(int i = 0; i < k; i++){
int u, v; cin >> u >> v;
Q.pb({u, v});
}
for(int i = 1; i <= n; i++){
cin >> A[i];
}
sort(E.begin(), E.end());
dsu_t.ini(n);
dsu_r.ini(n, A);
for(int i = 0; i < m; i++){
if(dsu_t.join(E[i].u, E[i].v)){
tmp.pb(E[i]);
}
}
swap(E, tmp); tmp.clear();
dsu_t.ini(n);
for(int i = 0; i < k; i++){
dsu_t.join(Q[i].u, Q[i].v);
}
assert(E.size() == n - 1);
for(int i = 0; i < n - 1; i++){
if(dsu_t.join(E[i].u, E[i].v)){
dsu_r.join(E[i].u, E[i].v);
}else{
tmp.pb(E[i]);
}
}
swap(E, tmp); tmp.clear();
for(auto& i : E) i.u = dsu_r.f(i.u), i.v = dsu_r.f(i.v);
for(auto& i : Q) i.u = dsu_r.f(i.u), i.v = dsu_r.f(i.v);
int rt;
{
set<int> S; map<int, int> M;
for(auto i : E) S.insert(i.u), S.insert(i.v);
for(auto i : Q) S.insert(i.u), S.insert(i.v);
int idx = 0; for(auto i : S) w[idx] = dsu_r.w[i], M[i] = idx++; r = idx;
for(auto& i : E) i.u = M[i.u], i.v = M[i.v];
for(auto& i : Q) i.u = M[i.u], i.v = M[i.v];
rt = M[dsu_r.f(1)];
}
int ans = 0;
for(uint mask = 0; mask < (1 << k); mask++){
dsu_t.ini(r, w), dsu_r.ini(r, w);
bool fail = false;
for(int i = 0; i < k; i++){
if(mask & (1 << i)){
if(!dsu_t.join(Q[i])) ubits[mask] = -1, fail = true;
}
}
if(fail) continue;
int ubit = 0;
for(int i = 0; i < E.size(); i++){
if(dsu_t.join(E[i])){
dsu_r.join(E[i]);
}else{
ubit |= (1 << i);
}
}
ubits[mask] = ubit;
for(int i = 0; i < k; i++){
if((1 << i) & mask){
uint df = ubits[mask] ^ ubits[mask ^ (1 << i)]; assert((ubits[mask] | ubits[mask ^ (1 << i)]) == ubits[mask]);
int idx = __builtin_ffs(df) - 1; assert(idx != -1);
wei[mask][i] = E[idx].w;
}
}
tQ = Q;
for(int i = 0; i < r; i++) H[i].clear();
for(int i = 0; i < k; i++){
if(mask & (1 << i)){
tQ[i].u = dsu_r.f(tQ[i].u), tQ[i].v = dsu_r.f(tQ[i].v), tQ[i].w = wei[mask][i];
H[tQ[i].u].pb({tQ[i].v, tQ[i].w});
H[tQ[i].v].pb({tQ[i].u, tQ[i].w});
}
}
ans = max(ans, dfs(dsu_r.f(rt)));
}
// for(int i = 0; i < (1 << k); i++){
// cout << ubits[i] << ' ';
// }
// cout << endl;
// for(int i = 0; i < (1 << k); i++){
// for(int j = 0; j < k; j++){
// cout << wei[i][j] << ' ';
// }
// cout << endl;
// }
// cout << r << endl;
// for(int i = 0; i < r; i++){
// cout << w[i] << ' ';
// }
// cout << endl;
// cout << "E" << endl;
// for(auto i : E){
// cout << i.u << ' ' << i.v << ' ' << i.w << endl;
// }
// cout << "Q" << endl;
// for(auto i : Q){
// cout << i.u << ' ' << i.v << ' ' << i.w << endl;
// }
cout << ans << endl;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from toll.cpp:1:
toll.cpp: In function 'int32_t main()':
toll.cpp:89:18: warning: comparison of integer expressions of different signedness: 'std::vector<edge>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
89 | assert(E.size() == n - 1);
| ~~~~~~~~~^~~~~~~~
toll.cpp:113:26: warning: comparison of integer expressions of different signedness: 'uint' {aka 'unsigned int'} and 'int' [-Wsign-compare]
113 | for(uint mask = 0; mask < (1 << k); mask++){
| ~~~~~^~~~~~~~~~
toll.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0; i < E.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2760 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
