oj.uz

Submission #986249

# Submission time Handle Problem Language Result Execution time Memory
986249 2024-05-20T06:58:15 Z vjudge1 Toll (APIO13_toll) C++17
16 / 100
 135 ms 163840 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 7<<10
#define int long long
vector<int> E,EEE;
set<pair<int,int>>adj[N];
int U[N],V[N],W[N],P[N],K,par[N],rem[N],res,ans;
int abp(int n){
    if(par[n]==n)
        return n;
    return par[n]=abp(par[n]);
}
bool dfs(int n,int p,int t){
    if(n==t)
        return 1;
    for(auto[i,j]:adj[n]){
        if(i==p)continue;
        if(dfs(i,n,t)) {
            if(W[res]<W[j])
                res=j;
            return 1;
        }
    }
    return 0;
}
void calc(int n,int p,int t){
    res+=P[n]*t;
    for(auto[i,j]:adj[n])if(i-p)
        calc(i,n,t+W[j]*(j<K));
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m>>K;
    while(m--) {
        cin>>U[m+K]>>V[m+K]>>W[m+K];
        E.push_back(m+K);
    }
    for(int i=0;i<K;i++)
        cin>>U[i]>>V[i];
    for(int i=0;i<n;)
        cin>>P[++i],par[i]=i;
    sort(E.begin(),E.end(),[](int a,int b){return W[a]<W[b];});
    for(auto i:E)
        if(abp(U[i])-abp(V[i]))
            par[par[U[i]]]=par[V[i]],
            EEE.push_back(i);
    E=EEE;
    for(auto i:E)
        adj[U[i]].insert({V[i],i}),
        adj[V[i]].insert({U[i],i});
    for(m=0;m<1<<K;m++){
        vector<int>R,ve;
        for(int i=1;i<=n;i++)
            par[i]=i;
        for(auto i:E)
            rem[i]=0;
        for(int i=0;i<K;i++)
            if(m&1<<i)
                ve.push_back(i);
        for(auto i:ve){
            dfs(U[i],0,V[i]),R.push_back(res);
            adj[U[i]].insert({V[i],i});
            adj[V[i]].insert({U[i],i});
            adj[U[res]].erase({V[res],res});
            adj[V[res]].erase({U[res],res});
            rem[res]=1,res=0;
        }
        for(auto j:E)
            if(rem[j]){
                int a=abp(U[j]),b=abp(V[j]);
                if(a>b)swap(a,b);
                while(1){
                    int ok=0;
                    for(int i=0;i<K;i++){
                        int c=abp(U[i]),d=abp(V[i]);
                        if(c>d)swap(c,d);
                        if(a==c&&b==d){
                            W[i]=W[j];
                            par[c]=d;
                            ok=1;
                            break;
                        }
                    }
                    if(!ok)
                        break;
                }
            } else par[abp(U[j])]=par[abp(V[j])];
        calc(1,0,0);
        ans=max(ans,res);
        res=0;
        for(auto i:R)adj[U[i]].insert({V[i],i}),
            adj[V[i]].insert({U[i],i});
        for(auto i:ve) adj[U[i]].erase({V[i],i}),
            adj[V[i]].erase({U[i],i});
    }
    cout<<ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 135 ms 163840 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 135 ms 163840 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 135 ms 163840 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Runtime error 135 ms 163840 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -