Submission #66646

#	Time	Username	Problem	Language	Result	Execution time	Memory
66646		Benq	Toll (APIO13_toll)	C++11	100 / 100	2024 ms	19020 KiB

toll

#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 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22