| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 973580 |
2024-05-02T07:40:07 Z |
socpite |
Toll (APIO13_toll) |
C++14 |
|
1063 ms |
24772 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+5;
const int INF = 1e9;
int n, m, k, cnt, rt;
int up1[maxn], up2[maxn];
int p_real[maxn], p[maxn], id[maxn], dep[maxn], par[maxn], mark[maxn], mn[maxn];
long long dp[maxn];
bool in_tree[maxn];
long long ans = 0;
int Find(int x, int* up){
return up[x] < 0 ? x : up[x] = Find(up[x], up);
}
bool Union(int a, int b, int* up){
a = Find(a, up);
b = Find(b, up);
if(a == b)return false;
up[a] += up[b];
up[b] = a;
return true;
}
vector<pair<int, int>> g[maxn];
vector<pair<int, pair<int, int>>> E1, E2, important;
vector<pair<int, int>> fake;
void pre_dfs(int x){
dp[x] = p_real[x];
mn[x] = 0;
for(auto v: g[x]){
if(v.first == par[x])continue;
dep[v.first] = dep[x] + 1;
par[v.first] = x;
pre_dfs(v.first);
dp[x] += dp[v.first];
mark[v.first] = v.second;
}
}
void solve(int mask){
for(int i = 1; i <= cnt; i++){
up1[i] = -1;
g[i].clear();
}
for(int i = 0; i < k; i++){
if(!(mask&(1<<i)))continue;
if(!Union(fake[i].first, fake[i].second, up1))return;
g[fake[i].first].push_back({fake[i].second, 1});
g[fake[i].second].push_back({fake[i].first, 1});
}
for(int i = 0; i < important.size(); i++){
auto v = important[i];
in_tree[i] = Union(v.second.first, v.second.second, up1);
if(in_tree[i]){
g[v.second.first].push_back({v.second.second, 0});
g[v.second.second].push_back({v.second.first, 0});
}
}
pre_dfs(rt);
for(int i = 0; i < important.size(); i++){
if(in_tree[i])continue;
int w = important[i].first, a = important[i].second.first, b = important[i].second.second;
// cout << w << " " << a << " " << b << endl;
while(a != b){
if(dep[a] < dep[b])swap(a, b);
if(!mn[a])mn[a] = w;
a = par[a];
}
}
long long sum = 0;
for(int i = 1; i <= cnt; i++){
// assert(mn[i] > 0 && dp[i] > 0);
if(mark[i])sum += 1LL*mn[i]*dp[i];
}
assert(sum >= 0);
ans = max(ans, sum);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
E1.resize(m);
for(auto &v: E1)cin >> v.second.first >> v.second.second >> v.first;
sort(E1.begin(), E1.end());
for(int i = 1; i <= n; i++)up1[i] = -1;
for(auto v: E1){
if(Union(v.second.first, v.second.second, up1))E2.push_back(v);
}
fake.resize(k);
for(auto &v: fake)cin >> v.first >> v.second;
for(int i = 1 ; i <= n; i++){
up1[i] = -1;
cin >> up2[i];
up2[i] *= -1;
}
for(auto v: fake)Union(v.first, v.second, up1);
for(auto v: E2){
if(Union(v.second.first, v.second.second, up1))Union(v.second.first, v.second.second, up2);
else important.push_back(v);
}
for(int i = 1; i <= n; i++){
if(up2[i] < 0){
cnt++;
id[i] = cnt;
p_real[cnt] = -up2[i];
assert(p_real[cnt] > 0);
}
}
rt = id[Find(1, up2)];
for(auto &v: fake){
v.first = id[Find(v.first, up2)];
v.second = id[Find(v.second, up2)];
// cout << v.first << " " << v.second << endl;
}
for(auto &v: important){
v.second.first = id[Find(v.second.first, up2)];
v.second.second = id[Find(v.second.second, up2)];
// cout << v.second.first << " " << v.second.second << endl;
}
for(int i = 1; i < (1<<k); i++)solve(i);
cout << ans;
}
Compilation message
toll.cpp: In function 'void solve(long long int)':
toll.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0; i < important.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
toll.cpp:68:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 0; i < important.size(); i++){
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 7 |
Correct |
123 ms |
24304 KB |
Output is correct |
| 8 |
Correct |
129 ms |
24256 KB |
Output is correct |
| 9 |
Correct |
133 ms |
24772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
7004 KB |
Output is correct |
| 6 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 7 |
Correct |
123 ms |
24304 KB |
Output is correct |
| 8 |
Correct |
129 ms |
24256 KB |
Output is correct |
| 9 |
Correct |
133 ms |
24772 KB |
Output is correct |
| 10 |
Correct |
826 ms |
24768 KB |
Output is correct |
| 11 |
Correct |
1014 ms |
24672 KB |
Output is correct |
| 12 |
Correct |
1063 ms |
24256 KB |
Output is correct |
