oj.uz

Submission #952040

# Submission time Handle Problem Language Result Execution time Memory
952040 2024-03-23T04:02:51 Z vjudge1 Training (IOI07_training) C++17
0 / 100
 300 ms 1628 KB 
#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]>to[b]||ti[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(){
    cin.tie(0)->sync_with_stdio(0);
    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(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1085 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -