oj.uz

답안 #66646

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

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4216 KB Output is correct
2 Correct 6 ms 4328 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

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

Subtask #5
22.0 / 22.0

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