Submission #952043

#	Time	Username	Problem	Language	Result	Execution time	Memory
952043		vjudge1	Training (IOI07_training)	C++17	37 / 100	14 ms	4700 KiB

training

#include<bits/stdc++.h>
using namespace std;
#define N 1024
#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>>b&1&&~i>>c&1)
            dp[n][i]=max(dp[n][i],a+dp[n][i|1<<b|1<<c]);
    }
}
int 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(int)':
training.cpp:34:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   34 |             else S3+=dp[p[a]][1<<find(all(adj[p[a]]),a)-adj[p[a]].begin()],a=p[a];
      |                                  ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:38:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |             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: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9