oj.uz

Submission #954979

# Submission time Handle Problem Language Result Execution time Memory
954979 2024-03-29T04:21:08 Z boyliguanhan Training (IOI07_training) C++17
100 / 100
 15 ms 4756 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4756 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1112 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 5 ms 1764 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2648 KB Output is correct
2 Correct 8 ms 1396 KB Output is correct
3 Correct 4 ms 1712 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1112 KB Output is correct
2 Correct 3 ms 1628 KB Output is correct
3 Correct 15 ms 4712 KB Output is correct
4 Correct 4 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2392 KB Output is correct
2 Correct 14 ms 4700 KB Output is correct
3 Correct 10 ms 1888 KB Output is correct
4 Correct 8 ms 1780 KB Output is correct