oj.uz

Submission #988494

# Submission time Handle Problem Language Result Execution time Memory
988494 2024-05-25T04:02:27 Z huutuan Training (IOI07_training) C++14
100 / 100
 9 ms 4952 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1010, M=5010;

int n, m, cnt_edge, dep[N], f[N][1024], par[N];
vector<int> g[N];
vector<int> vv[N];
pair<pair<int, int>, int> edge[M];

void pre_dfs(int u, int p){
   dep[u]=dep[p]+1;
   par[u]=p;
   if (p) g[u].erase(find(g[u].begin(), g[u].end(), p));
   for (int v:g[u]) pre_dfs(v, u);
}

int lca(int u, int v){
   if (dep[u]>dep[v]) swap(u, v);
   while (dep[u]!=dep[v]){
      v=par[v];
   }
   while (u!=v){
      u=par[u]; v=par[v];
   }
   return u;
}

int idx[N], cnt[N];

void dfs(int u){
   for (int v:g[u]) dfs(v);
   cnt[u]=(int)g[u].size();
   for (int i=0; i<cnt[u]; ++i) idx[g[u][i]]=i;
   for (int i=0; i<cnt[u]; ++i) f[u][1<<i]=f[g[u][i]][(1<<cnt[g[u][i]])-1];
   for (int _:vv[u]){
      int v1=edge[_].first.first, v2=edge[_].first.second, w=edge[_].second;
      if (v2==u) swap(v1, v2);
      if (v1==u){
         int sum=0, lst=-1;
         while (v2!=u){
            if (lst==-1) sum+=f[v2][(1<<cnt[v2])-1];
            else sum+=f[v2][((1<<cnt[v2])-1)^(1<<idx[lst])];
            lst=v2; v2=par[v2];
         }
         f[u][1<<idx[lst]]=max(f[u][1<<idx[lst]], sum+w);
      }else{
         int sum=0, lst1=-1, lst2=-1;
         while (v1!=u){
            if (lst1==-1) sum+=f[v1][(1<<cnt[v1])-1];
            else sum+=f[v1][((1<<cnt[v1])-1)^(1<<idx[lst1])];
            lst1=v1; v1=par[v1];
         }
         while (v2!=u){
            if (lst2==-1) sum+=f[v2][(1<<cnt[v2])-1];
            else sum+=f[v2][((1<<cnt[v2])-1)^(1<<idx[lst2])];
            lst2=v2; v2=par[v2];
         }
         f[u][(1<<idx[lst1])|(1<<idx[lst2])]=max(f[u][(1<<idx[lst1])|(1<<idx[lst2])], sum+w);
      }
   }
   for (int i=0; i<(1<<cnt[u]); ++i){
      for (int j=(i-1)&i; ; j=(j-1)&i){
         f[u][i]=max(f[u][i], f[u][j]+f[u][i^j]);
         if (!j) break;
      }
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   int ans=0;
   for (int i=1; i<=m; ++i){
      int u, v, w; cin >> u >> v >> w;
      if (w) edge[++cnt_edge]={{u, v}, w}, ans+=w;
      else g[u].push_back(v), g[v].push_back(u);
   }
   pre_dfs(1, 0);
   for (int i=1; i<=cnt_edge; ++i) if ((dep[edge[i].first.first]&1)==(dep[edge[i].first.second]&1)){
      vv[lca(edge[i].first.first, edge[i].first.second)].push_back(i);
   }
   dfs(1);
   cout << ans-f[1][(1<<cnt[1])-1] << '\n';
   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 5 ms 4696 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 3 ms 2392 KB Output is correct
3 Correct 8 ms 4700 KB Output is correct
4 Correct 4 ms 2576 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4952 KB Output is correct
2 Correct 9 ms 4628 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct