Submission #131810

#	Time	Username	Problem	Language	Result	Execution time	Memory
131810		futurer	Toll (APIO13_toll)	C++14	78 / 100	2526 ms	43140 KiB

toll

// in the name of ALLAH
#pragma GCC optimize "-O3"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e6+5, M = 1e6+5, L = 22, inf = 1e8;
ll W[N], SZ[N], rt;
int D[N], C[M], PR[M], A[M], B[M], dp[N], H[N], P[N], n, m, k, pr, cent;
vector<int> adj[N], v;
int get(int a) { return(!D[a]?a:D[a]=get(D[a])); }
void merg(int a, int b){
    a=get(a); b=get(b);
    if(a^b) D[b]=a;
}
bitset<M> AYA, DID;
bool cmp(int&a, int&b) { return(C[a]<C[b]); }
void DFS(int u){
    DID[u]=1;
    W[cent]+=W[u];
    merg(cent, u);
    for(int x:adj[u]) if(!DID[x]) DFS(x);
}
void DFS2(int u, int p){
    H[u]=H[P[u]=p]+1;
    for(int x:adj[u]) if(A[x]^B[x]^u^p){
        int to=A[x]^B[x]^u;
        if(x>=m) dp[to]=inf;
        DFS2(to, u);
    }
}
ll DFS3(int u, int p){
    ll ah=0;
    SZ[u]=W[u];
    for(int x:adj[u]) if(A[x]^B[x]^u^p){
        int to=A[x]^B[x]^u;
        ah+=DFS3(to, u);
        ah+=1LL*SZ[to]*dp[to];
        SZ[u]+=SZ[to];
    }
    return(ah);
}
void ah() { cerr << "!!!\n"; }
int32_t main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=0;i<m;i++){
        scanf("%d %d %d", &A[i], &B[i], &C[i]);
        PR[pr++]=i;
    }
    for(int i=m;i<m+k;i++) scanf("%d %d", &A[i], &B[i]);
    for(int i=1;i<=n;i++) scanf("%lld", &W[i]);
    sort(PR, PR+pr, cmp);
    for(int i=0;i<pr;i++) if(get(A[PR[i]])^get(B[PR[i]])){
        merg(A[PR[i]], B[PR[i]]);
        AYA[PR[i]]=1;
    }
    memset(D, 0, sizeof(D));
    for(int i=m;i<m+k;i++) PR[pr++]=i;
    sort(PR, PR+pr, cmp);
    for(int i=0;i<pr;i++) if(get(A[PR[i]])^get(B[PR[i]])){
        merg(A[PR[i]], B[PR[i]]);
        if(PR[i]<m){
            adj[A[PR[i]]].push_back(B[PR[i]]);
            adj[B[PR[i]]].push_back(A[PR[i]]);
        }
    }
    memset(D, 0, sizeof(D));
    cent=n;
    for(int i=1;i<=n;i++) if(!DID[i]) { cent++; DFS(i); }
    for(int i=0;i<N;i++) while(adj[i].size()) adj[i].pop_back();
    for(int i=0;i<m+k;i++){
        A[i]=get(A[i]);
        B[i]=get(B[i]);
    }
    for(int i=0;i<m;i++) if(AYA[i]&&(A[i]^B[i])){
        v.push_back(i);
    }
    memset(D, 0, sizeof(D));
    for(int msk=0;msk<(1<<k);msk++){
        vector<int> v2;
        for(int i=n+1;i<=cent;i++){
            D[i]=0;
            dp[i]=-1;
            while(adj[i].size()) adj[i].pop_back();
        }
        pr=0;
        for(int i=0;i<k;i++) if(msk&(1<<i)) PR[pr++]=m+i;
        for(int x:v) PR[pr++]=x;
        sort(PR, PR+pr, cmp);
        bool f=0;
        for(int i=0;i<pr;i++){
            if(get(A[PR[i]])^get(B[PR[i]])){
                merg(A[PR[i]], B[PR[i]]);
                adj[A[PR[i]]].push_back(PR[i]);
                adj[B[PR[i]]].push_back(PR[i]);
            }
            else{
                if(!AYA[PR[i]]) { f=1; continue; }
                v2.push_back(PR[i]);
            }
        }
        if(f) continue;
        DFS2(n+1, 0);
        for(int x:v2){
            int a=A[x], b=B[x];
            while(H[a]>H[b]) { dp[a]=min(dp[a], C[x]); a=P[a]; }
            while(H[b]>H[a]) { dp[b]=min(dp[b], C[x]); b=P[b]; }
            while(a^b){
                dp[a]=min(dp[a], C[x]); dp[b]=min(dp[b], C[x]);
                a=P[a]; b=P[b];
            }
        }
        for(int i=n+1;i<=cent;i++) if(!(~dp[i])) dp[i]=0;
        rt=max(rt, DFS3(n+1, 0));
    }
    printf("%lld", rt);
}

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &A[i], &B[i], &C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:50:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=m;i<m+k;i++) scanf("%d %d", &A[i], &B[i]);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:51:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld", &W[i]);
                           ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 0 / 22