| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1022055 |
2024-07-13T09:25:27 Z |
awu |
Toll (APIO13_toll) |
C++14 |
|
2500 ms |
20464 KB |
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;
template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
out << "(" << p.f << ", " << p.s << ")";
return out;
}
template<typename T>
typename enable_if<!is_same<T, const char *>::value && !is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T o) {
out << "{";
int g = o.size();
for(auto i : o) out << i << (--g ? ", " : "");
out << "}";
return out;
}
void my_assert(bool b) {
if(!b) {
cerr << "Assertion failed" << endl;
*((volatile int*)0);
}
}
#undef assert
#define assert my_assert
struct dsu {
vector<int> p, r;
bool bad = false;
vector<int> stac;
dsu(int n) {
p.resize(n);
iota(all(p), 0);
r.resize(n);
for(int i = 1; i < n; i++) r[i] = rand();
}
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(r[x] < r[y]) swap(x, y);
if(x == y) {
// debug("BAD");
bad = true;
}
p[x] = y;
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k; cin >> n >> m >> k;
struct edge {
int a, b, c;
};
vector<edge> el(m);
for(int i = 0; i < m; i++) {
cin >> el[i].a >> el[i].b >> el[i].c; el[i].a--; el[i].b--;
}
sort(all(el), [&](edge a, edge b) {
return a.c < b.c;
});
vector<pii> kl(k);
for(int i = 0; i < k; i++) {
cin >> kl[i].f >> kl[i].s; kl[i].f--; kl[i].s--;
}
vector<int> p(n);
for(int i = 0; i < n; i++) {
cin >> p[i];
}
vector<edge> el2;
dsu uf(n);
for(auto [a, b, c] : el) {
if(uf.find(a) != uf.find(b)) {
uf.merge(a, b);
el2.push_back({a, b, c});
}
}
uf = dsu(n);
el = el2;
el2.clear();
for(auto [a, b] : kl) {
uf.merge(a, b);
}
vector<edge> el3;
vector<vector<int>> adj(n);
for(auto [a, b, c] : el) {
if(uf.find(a) != uf.find(b)) {
uf.merge(a, b);
el2.push_back({a, b, c});
} else {
el3.push_back({a, b, c});
}
}
el = el3;
uf = dsu(n);
for(auto [a, b, c] : el2) {
uf.merge(a, b);
}
vector<int> cc;
for(int i = 0; i < n; i++) {
cc.push_back(uf.find(i));
if(uf.find(i) != i) {
p[uf.find(i)] += p[i];
}
}
sort(all(cc));
cc.erase(unique(all(cc)), cc.end());
for(int i = 0; i < el.size(); i++) {
el[i].a = lower_bound(all(cc), uf.find(el[i].a)) - cc.begin();
el[i].b = lower_bound(all(cc), uf.find(el[i].b)) - cc.begin();
}
for(int i = 0; i < kl.size(); i++) {
kl[i].f = lower_bound(all(cc), uf.find(kl[i].f)) - cc.begin();
kl[i].s = lower_bound(all(cc), uf.find(kl[i].s)) - cc.begin();
}
n = cc.size();
m = el.size();
vector<int> p2(n);
for(int i = 0; i < n; i++) {
p2[i] = p[cc[i]];
}
p = p2;
int ans = 0;
vector<bool> bad(1 << k);
for(int msk = 0; msk < 1 << k; msk++) {
dsu uf(n);
for(int i = 0; i < k; i++) {
if(msk & (1 << i)) {
uf.merge(kl[i].f, kl[i].s);
}
}
bad[msk] = uf.bad;
}
{
function<void(int, int, vector<vector<int>>)> dfs = [&](int msk, int i, vector<vector<int>> adj) {
if(i == k) {
for(int i = 0; i < n; i++) {
for(auto& w : adj[i]) {
if(w < 0) w = -w;
else w = 0;
}
}
int acc = 0;
function<int(int, int)> dfs = [&](int cur, int par) {
int ss = p[cur];
for(int i = 0; i < adj[cur].size(); i++) {
if(i == par) continue;
if(adj[cur][i] == inf) continue;
int cs = dfs(i, cur);
acc += cs * adj[cur][i];
ss += cs;
}
return ss;
};
dfs(0, -1);
ans = max(ans, acc);
return;
}
{
int a, b; tie(a, b) = kl[i];
int mx = 0;
vector<int> path;
function<bool(int, int)> dfs = [&](int cur, int par) {
path.push_back(cur);
if(cur == b) return true;
for(int i = 0; i < adj[cur].size(); i++) {
if(i == par) continue;
if(adj[cur][i] == -inf) continue;
if(dfs(i, cur)) {
mx = max(mx, adj[cur][i]);
return true;
}
}
path.pop_back();
return false;
};
dfs(a, -1);
for(int j = 0; j < path.size() - 1; j++) {
if(adj[path[j]][path[j + 1]] < 0) {
adj[path[j]][path[j + 1]] = max(adj[path[j]][path[j + 1]], -mx);
adj[path[j + 1]][path[j]] = max(adj[path[j + 1]][path[j]], -mx);
}
if(adj[path[j]][path[j + 1]] == mx) {
adj[path[j]][path[j + 1]] = -inf;
adj[path[j + 1]][path[j]] = -inf;
}
}
adj[a][b] = -mx;
adj[b][a] = -mx;
}
for(int j = i + 1; j <= k; j++) {
dfs(msk ^ (1 << i), j, adj);
}
};
vector<vector<int>> adj(n, vector<int>(n, -inf)); // k edges have negative weight for now
for(auto [a, b, c] : el) {
adj[a][b] = adj[b][a] = c;
}
for(int i = 0; i < k; i++) {
dfs(0, i, adj);
}
}
cout << ans << endl;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:87:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for(auto [a, b, c] : el) {
| ^
toll.cpp:96:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for(auto [a, b] : kl) {
| ^
toll.cpp:101:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | for(auto [a, b, c] : el) {
| ^
toll.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
111 | for(auto [a, b, c] : el2) {
| ^
toll.cpp:123:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<main()::edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int i = 0; i < el.size(); i++) {
| ~~^~~~~~~~~~~
toll.cpp:127:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int i = 0; i < kl.size(); i++) {
| ~~^~~~~~~~~~~
toll.cpp: In lambda function:
toll.cpp:161:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int i = 0; i < adj[cur].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
toll.cpp: In lambda function:
toll.cpp:181:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for(int i = 0; i < adj[cur].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
toll.cpp: In lambda function:
toll.cpp:193:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | for(int j = 0; j < path.size() - 1; j++) {
| ~~^~~~~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:211:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
211 | for(auto [a, b, c] : el) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
472 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
472 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
472 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
189 ms |
20308 KB |
Output is correct |
| 8 |
Correct |
175 ms |
20400 KB |
Output is correct |
| 9 |
Correct |
201 ms |
20388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
472 KB |
Output is correct |
| 4 |
Correct |
2 ms |
476 KB |
Output is correct |
| 5 |
Correct |
3 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
189 ms |
20308 KB |
Output is correct |
| 8 |
Correct |
175 ms |
20400 KB |
Output is correct |
| 9 |
Correct |
201 ms |
20388 KB |
Output is correct |
| 10 |
Execution timed out |
2531 ms |
20464 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
