| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66646 |
2018-08-11T21:27:48 Z |
Benq |
Toll (APIO13_toll) |
C++11 |
|
2024 ms |
19020 KB |
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
int N,M,K, people[MX], comp[MX];
ll sumPeople[22];
template<int SZ> struct DSU {
int par[SZ], sz[SZ];
DSU() {
F0R(i,SZ) par[i] = i, sz[i] = 1;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], par[y] = x;
return 1;
}
};
DSU<MX> D[2];
vector<array<int,3>> ed, posi[2];
vpi adj[MX];
void addEdge(array<int,3> a) {
adj[a[1]].pb({a[2],a[0]});
adj[a[2]].pb({a[1],a[0]});
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
F0R(i,M) {
int a,b,c;
/*b = i+2;
a = rand() % (i+1)+1;
c = rand() % 1000000;*/
cin >> a >> b >> c;
ed.pb({c,a,b});
}
sort(all(ed));
F0R(i,K) {
// int x = rand() % N+1, y = rand() % N+1;
int x,y; cin >> x >> y;
posi[0].pb({-1,x,y});
D[0].unite(x,y);
}
FOR(i,1,N+1) {
// people[i] = rand() % 1000000;
cin >> people[i];
}
for (auto a: ed) if (D[0].unite(a[1],a[2])) {
addEdge(a);
D[1].unite(a[1],a[2]);
}
int co = 0;
map<int,int> tmp;
FOR(i,1,N+1) {
if (!tmp.count(D[1].get(i))) tmp[D[1].get(i)] = ++co;
comp[i] = tmp[D[1].get(i)];
sumPeople[comp[i]] += people[i];
}
for (auto a: ed) if (D[1].unite(a[1],a[2])) posi[1].pb(a);
}
vpi ADJ[22];
int depth[22];
pi par[22];
void Addedge(int u, int v, int d) {
ADJ[comp[u]].pb({comp[v],d});
ADJ[comp[v]].pb({comp[u],d});
}
void dfs2(int x) {
for (auto a: ADJ[x]) if (a.f != par[x].f) {
par[a.f] = {x,a.s};
depth[a.f] = depth[x]+1; dfs2(a.f);
}
}
template<class T> void mn(T& a, T b) { a = min(a,b); }
void doSmth(array<int,3> a) {
a[1] = comp[a[1]], a[2] = comp[a[2]];
while (a[1] != a[2]) {
if (depth[a[1]] < depth[a[2]]) swap(a[1],a[2]);
mn(par[a[1]].s,a[0]);
a[1] = par[a[1]].f;
}
}
ll ans = 0, ret = 0;
void finish(int x, ll cdist = 0) {
ret += sumPeople[x]*cdist;
for (auto a: ADJ[x]) if (a.f != par[x].f)
finish(a.f,cdist+par[a.f].s);
}
void tri(int x) {
FOR(i,1,K+2) ADJ[i].clear();
DSU<22> D = DSU<22>();
F0R(j,K) if (x&(1<<j)) {
if (!D.unite(comp[posi[0][j][1]],comp[posi[0][j][2]])) return;
Addedge(posi[0][j][1],posi[0][j][2],MOD);
}
vector<array<int,3>> bad;
for (auto a: posi[1]) {
if (D.unite(comp[a[1]],comp[a[2]])) Addedge(a[1],a[2],0);
else bad.pb(a);
}
dfs2(1);
for (auto a: bad) doSmth(a);
ret = 0;
finish(1);
ans = max(ans,ret);
}
int main() {
init();
// cout << sumPeople[1] << " " << peopleDist[0] << "\n";
// FOR(i,1,N+1) cout << comp[i] << " ";
// cout << "\n";
F0R(i,1<<K) tri(i);
cout << ans;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4328 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4404 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4328 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4404 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
9 ms |
4628 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4328 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4404 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
9 ms |
4628 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4628 KB |
Output is correct |
| 7 |
Correct |
253 ms |
12584 KB |
Output is correct |
| 8 |
Correct |
295 ms |
12584 KB |
Output is correct |
| 9 |
Correct |
276 ms |
12584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4328 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4404 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
9 ms |
4628 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4628 KB |
Output is correct |
| 7 |
Correct |
253 ms |
12584 KB |
Output is correct |
| 8 |
Correct |
295 ms |
12584 KB |
Output is correct |
| 9 |
Correct |
276 ms |
12584 KB |
Output is correct |
| 10 |
Correct |
1334 ms |
12584 KB |
Output is correct |
| 11 |
Correct |
2023 ms |
12584 KB |
Output is correct |
| 12 |
Correct |
2024 ms |
19020 KB |
Output is correct |
