Submission #819714

#	Time	Username	Problem	Language	Result	Execution time	Memory
819714		Ahmed57	Training (IOI07_training)	C++17	100 / 100	15 ms	4668 KiB

training

#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 (stderr)

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 / 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