oj.uz

Submission #819714

# Submission time Handle Problem Language Result Execution time Memory
819714 2023-08-10T12:50:39 Z Ahmed57 Training (IOI07_training) C++17
100 / 100
 15 ms 4668 KB 
#include <bits/stdc++.h>

using namespace std;
long long dp[5001][(1<<10)];
int in[5001],ou[5001],lol[5001],deg[5001];
vector<int> adj[5001];pair<int,int> pr[5001];
struct road{
    int l,r,cost,lca;
};
bool operator<(road a,road b){
    return ou[a.lca]<ou[b.lca];
}
int timer = 0;
void dfs(int i,int Pr){
    in[i] = ++timer;
    lol[i] = lol[Pr]^1;
    for(auto j:adj[i]){
        if(j!=Pr){
            pr[j] = {i,(1<<deg[i])};
            deg[i]++;
            dfs(j,i);
        }
    }
    ou[i] = ++timer;
}
bool ispar(int A,int B){
    return ((in[A]<=in[B]&&ou[A]>=ou[B]));
}
int lca(int A,int B){
    while(!ispar(A,B))A = pr[A].first;
    return A;
}
int main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<road> v;
    long long all = 0;
    for(int i = 0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;all+=c;
        if(!c){
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        v.push_back({a,b,c});
    }
    dfs(1,0);
    for(int i = 0;i<v.size();i++){
        v[i].lca = lca(v[i].l,v[i].r);
    }
    sort(v.begin(),v.end());
    for(auto i:v){
        if(i.cost&&(lol[i.l]^lol[i.r])==1)continue;
        long long xd = i.cost;
        pair<int,int> A , B;
        for(A = {i.l,0};A.first!=i.lca;A = pr[A.first])xd+=dp[A.first][A.second];
        for(B = {i.r,0};B.first!=i.lca;B = pr[B.first])xd+=dp[B.first][B.second];
        for(int mask = (1<<deg[i.lca])-1;~mask;mask--){
            if((mask&(A.second|B.second))==0){
            dp[i.lca][mask] = max(dp[i.lca][mask],xd+dp[i.lca][mask|A.second|B.second]);
            }
        }
    }
    cout<<all-dp[1][0]<<endl;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4656 KB Output is correct
2 Correct 7 ms 4564 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2260 KB Output is correct
2 Correct 5 ms 1364 KB Output is correct
3 Correct 4 ms 1620 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 956 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 15 ms 4564 KB Output is correct
4 Correct 4 ms 1748 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2260 KB Output is correct
2 Correct 14 ms 4668 KB Output is correct
3 Correct 6 ms 1876 KB Output is correct
4 Correct 5 ms 1620 KB Output is correct