Submission #954979

#	Time	Username	Problem	Language	Result	Execution time	Memory
954979		boyliguanhan	Training (IOI07_training)	C++17	100 / 100	15 ms	4756 KiB

training

#include<bits/stdc++.h>
using namespace std;
#define N 1024
#define int long long
#define all(x) begin(x),end(x)
vector<tuple<int,int,int>>tp;
vector<int>adj[N];
vector<tuple<int,int,int>> goth[N];
int dep[N],dp[N][N],p[N],ti[N],to[N],cnt;
void dfs(int n){
    ti[n]=++cnt;
    if(p[n])adj[n].erase(find(all(adj[n]),p[n]));
    for(auto i:adj[n])
        p[i]=n,dep[i]=dep[n]+1,dfs(i);
    to[n]=cnt;
}
int lca(int a,int b) {
    while(!(ti[a]<=ti[b]&&to[b]<=to[a]))
        a=p[a];
    return a;
}
void calcdp(int n){
    for(auto i:adj[n])
        calcdp(i);
    int sz=goth[n].size();
    vector<tuple<int,int,int>>details(sz,{0,10,10});
    for(int i=0;i<sz;i++) {
        auto[a,b,c]=goth[n][i];
        int S3=c;
        if(a-n) S3+=dp[a][0];
        if(b-n) S3+=dp[b][0];
        while(a!=n)
            if(p[a]==n)
                get<1>(details[i])=find(all(adj[n]),a)-adj[n].begin(),a=n;
            else S3+=dp[p[a]][1<<find(all(adj[p[a]]),a)-adj[p[a]].begin()],a=p[a];
        while(b!=n)
            if(p[b]==n)
                get<2>(details[i])=find(all(adj[n]),b)-adj[n].begin(),b=n;
            else S3+=dp[p[b]][1<<find(all(adj[p[b]]),b)-adj[p[b]].begin()],b=p[b];
        get<0>(details[i])=S3;
    }
    int bits=adj[n].size();
    for(int i=1<<bits;i--;){
        for(int j=0;j<bits;j++)
            dp[n][i]+=(~(i>>j)&1)*dp[adj[n][j]][0];
        for(auto[a,b,c]:details) if(~i&1<<b&&~i&1<<c)
            dp[n][i]=max(dp[n][i],a+dp[n][i+(b<10?1<<b:0)+(c<10?1<<c:0)]);
    }
}
signed main(){
    int n,m,W=0;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(!c) adj[a].push_back(b),
            adj[b].push_back(a);
        else tp.push_back({a,b,c});
        W+=c;
    }
    dfs(1);
    for(auto [a,b,w]:tp)
        if(~(dep[a]+dep[b])&1)
            goth[lca(a,b)].push_back({a,b,w});
    calcdp(1);
    cout<<W-*dp[1];
}

Compilation message (stderr)

training.cpp: In function 'void calcdp(long long int)':
training.cpp:35:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |             else S3+=dp[p[a]][1<<find(all(adj[p[a]]),a)-adj[p[a]].begin()],a=p[a];
      |                                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:39:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |             else S3+=dp[p[b]][1<<find(all(adj[p[b]]),b)-adj[p[b]].begin()],b=p[b];
      |                                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9