| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 384775 |
2021-04-02T09:02:12 Z |
aarr |
Toll (APIO13_toll) |
C++14 |
|
4 ms |
5100 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100 * 1000 + 5, M = 300 * 1000 + 5;
int st[M], ed[M];
pair <int, int> e[M];
int a[N];
vector <pair <int, int> > adj[N];
vector <int> vec[N];
int par[N], sz[N];
vector <int> cl;
bool mark[N];
int sm[N];
long long dp[N];
int get_par(int v) {
if (par[v] == v) {
return v;
}
return get_par(par[v]);
}
void dfs(int v, int mask) {
mark[v] = true;
cl.push_back(v);
sm[v] = sz[v];
for (auto p : adj[v]) {
int t = p.second, u = get_par(p.first);
if (!mark[u] && ((mask >> t) & 1)) {
dfs(u, mask);
sm[v] += sm[u];
dp[v] += dp[u];
dp[v] += sm[u];
}
}
}
int32_t main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> st[i] >> ed[i] >> e[i].first;
e[i].second = i;
}
sort(e + 1, e + m + 1);
for (int i = 0; i < k; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for (int i = 1; i <= n; i++) {
cin >> sz[i];
par[i] = i;
}
for (int mask = 0; mask < (1 << k); mask++) {
int x = __builtin_popcount(mask);
if (n - x - 1 >= 0) {
vec[n - x - 1].push_back(mask);
}
}
int cnt = 0;
long long ans = 0;
// cout << "75 " << endl;
for (int i = 1; i <= m; i++) {
int u = get_par(st[e[i].second]), v = get_par(ed[e[i].second]);
if (u != v) {
if (adj[v].size() > adj[u].size()) {
swap(u, v);
}
for (auto x : vec[cnt]) {
// cout << "71 " << cnt << " " << x << endl;
int v = get_par(1);
dfs(v, x);
// for (int j = 1; j <= n; j++) {
// cout << "72 " << j << " " << par[j] << " " << sm[j] << " " << dp[j] << endl;
// }
if (cl.size() + cnt == n) {
ans = max(ans, 1ll * dp[v] * e[i].first);
}
for (auto x : cl) {
mark[x] = false;
dp[x] = sm[x] = false;
}
cl.clear();
}
par[v] = u;
sz[u] += sz[v];
// for (int j = 1; j <= n; j++) {
// cout << "74 " << j << " " << par[j] << " " << sm[j] << " " << dp[j] << endl;
// }
for (auto x : adj[v]) {
adj[u].push_back(x);
}
cnt++;
}
}
cout << ans;
return 0;
}
Compilation message
toll.cpp: In function 'int32_t main()':
toll.cpp:82:25: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
82 | if (cl.size() + cnt == n) {
| ~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
