| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1022271 |
2024-07-13T11:47:42 Z |
awu |
Toll (APIO13_toll) |
C++14 |
|
1066 ms |
23300 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;
for(int msk = 0; msk < 1 << k; msk++) {
if(k > 15 && __builtin_popcount(msk) < k * 0.6) continue;
dsu uf(n);
vector<vector<pii>> adj(n);
for(int i = 0; i < k; i++) {
if(msk & (1 << i)) {
uf.merge(kl[i].f, kl[i].s);
adj[kl[i].f].push_back({kl[i].s, -1});
adj[kl[i].s].push_back({kl[i].f, -1});
}
}
if(uf.bad) continue;
int dc = 0;
for(int i = 0; i < m; i++) {
auto [a, b, c] = el[i];
if(uf.find(a) == uf.find(b)) {
if(dc == __builtin_popcount(msk)) continue;
int B = b;
int C = c;
function<bool(int, int)> dfs = [&](int cur, int par) {
if(cur == B) return true;
for(auto& [i, w] : adj[cur]) {
if(i == par) continue;
if(dfs(i, cur)) {
if(w == -1) {
dc++;
w = C;
for(int j = 0; j < adj[i].size(); j++) {
if(adj[i][j].f == cur) {
adj[i][j].s = C;
break;
}
}
}
return true;
}
}
return false;
};
dfs(a, -1);
} else {
adj[a].push_back({b, 0});
adj[b].push_back({a, 0});
uf.merge(a, b);
}
}
int acc = 0;
function<int(int, int)> dfs = [&](int cur, int par) {
int ss = p[cur];
for(auto i : adj[cur]) {
if(i.f == par) continue;
int cs = dfs(i.f, cur);
acc += cs * i.s;
ss += cs;
}
return ss;
};
dfs(0, -1);
ans = max(ans, acc);
}
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:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | auto [a, b, c] = el[i];
| ^
toll.cpp: In lambda function:
toll.cpp:160:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
160 | for(auto& [i, w] : adj[cur]) {
| ^
toll.cpp:166:34: 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]
166 | for(int j = 0; j < adj[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
752 KB |
Output is correct |
| 7 |
Correct |
143 ms |
23172 KB |
Output is correct |
| 8 |
Correct |
164 ms |
23300 KB |
Output is correct |
| 9 |
Correct |
165 ms |
23204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
2 ms |
752 KB |
Output is correct |
| 7 |
Correct |
143 ms |
23172 KB |
Output is correct |
| 8 |
Correct |
164 ms |
23300 KB |
Output is correct |
| 9 |
Correct |
165 ms |
23204 KB |
Output is correct |
| 10 |
Correct |
541 ms |
23200 KB |
Output is correct |
| 11 |
Correct |
1066 ms |
23204 KB |
Output is correct |
| 12 |
Correct |
946 ms |
23300 KB |
Output is correct |
