oj.uz

답안 #66645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66645 2018-08-11T21:14:29 Z Benq 통행료 (APIO13_toll) C++11
78 / 100
 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 :/
*/

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12360 KB Output is correct
2 Correct 12 ms 12360 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 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

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 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

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 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 -