| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 66645 |
2018-08-11T21:14:29 Z |
Benq |
Toll (APIO13_toll) |
C++11 |
|
2500 ms |
143688 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;
vector<array<int,3>> posi[2];
vpi adj[MX];
vector<array<ll,MX>> dist;
vl peopleDist;
int m[MX];
void addEdge(array<int,3> a) {
adj[a[1]].pb({a[2],a[0]});
adj[a[2]].pb({a[1],a[0]});
}
void dfs(int x, int p, ll cdist) {
dist.back()[x] = cdist;
peopleDist.back() += people[x]*cdist;
for (auto a: adj[x]) if (a.f != p) dfs(a.f,x,cdist+a.s);
}
void genDist(int x) {
if (m[x] != -1) return;
m[x] = sz(dist);
dist.pb(array<ll,MX>());
peopleDist.pb(0);
dfs(x,0,0);
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
F0R(i,M) {
int a,b,c; cin >> a >> b >> c;
ed.pb({c,a,b});
}
sort(all(ed));
F0R(i,K) {
int x,y; cin >> x >> y;
posi[0].pb({-1,x,y});
D[0].unite(x,y);
}
FOR(i,1,N+1) 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);
FOR(i,1,N+1) m[i] = -1;
genDist(1);
F0R(i,2) for (auto a: posi[i]) genDist(a[1]), genDist(a[2]);
}
vector<array<int,3>> ADJ[22];
int depth[22], ok[22];
array<int,3> par[22];
void Addedge(int u, int v, int d) {
ADJ[comp[u]].pb({u,v,d});
ADJ[comp[v]].pb({v,u,d});
}
void dfs2(int x) {
for (auto a: ADJ[x]) if (comp[a[1]] != comp[par[x][0]]) {
par[comp[a[1]]] = a;
depth[comp[a[1]]] = depth[x]+1;
dfs2(comp[a[1]]);
}
}
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]];
// cout << "ZZ " << a[0] << " " << a[1] << " " << a[2] << "\n";
while (a[1] != a[2]) {
if (depth[a[1]] < depth[a[2]]) swap(a[1],a[2]);
// cout << "OH " << par[a[1]][2] << "\n";
mn(par[a[1]][2],a[0]);
// cout << "OH " << par[a[1]][2] << "\n";
a[1] = comp[par[a[1]][0]];
}
}
ll ans = 0, ret = 0;
void finish(int x, ll cdist = 0) {
// cout << people[comp[x]] << " " << cdist << "\n";
ret += sumPeople[comp[x]]*cdist;
for (auto a: ADJ[comp[x]]) if (comp[a[1]] != comp[par[comp[x]][0]])
finish(a[1],cdist+par[comp[a[1]]][2]);
}
void tri(int x) {
FOR(i,1,K+2) {
ADJ[i].clear();
par[i] = {0,0,0};
ok[i] = 0;
}
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);
// cout << "HA " << ret << "\n";
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 |
13 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12360 KB |
Output is correct |
| 3 |
Correct |
41 ms |
31396 KB |
Output is correct |
| 4 |
Correct |
24 ms |
31396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12360 KB |
Output is correct |
| 3 |
Correct |
41 ms |
31396 KB |
Output is correct |
| 4 |
Correct |
24 ms |
31396 KB |
Output is correct |
| 5 |
Correct |
79 ms |
56920 KB |
Output is correct |
| 6 |
Correct |
47 ms |
56920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12360 KB |
Output is correct |
| 3 |
Correct |
41 ms |
31396 KB |
Output is correct |
| 4 |
Correct |
24 ms |
31396 KB |
Output is correct |
| 5 |
Correct |
79 ms |
56920 KB |
Output is correct |
| 6 |
Correct |
47 ms |
56920 KB |
Output is correct |
| 7 |
Correct |
534 ms |
74064 KB |
Output is correct |
| 8 |
Correct |
387 ms |
80444 KB |
Output is correct |
| 9 |
Correct |
416 ms |
87012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12360 KB |
Output is correct |
| 3 |
Correct |
41 ms |
31396 KB |
Output is correct |
| 4 |
Correct |
24 ms |
31396 KB |
Output is correct |
| 5 |
Correct |
79 ms |
56920 KB |
Output is correct |
| 6 |
Correct |
47 ms |
56920 KB |
Output is correct |
| 7 |
Correct |
534 ms |
74064 KB |
Output is correct |
| 8 |
Correct |
387 ms |
80444 KB |
Output is correct |
| 9 |
Correct |
416 ms |
87012 KB |
Output is correct |
| 10 |
Correct |
2128 ms |
143688 KB |
Output is correct |
| 11 |
Execution timed out |
2511 ms |
143688 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
