oj.uz

Submission #134055

# Submission time Handle Problem Language Result Execution time Memory
134055 2019-07-22T02:50:00 Z dragonslayerit Training (IOI07_training) C++14
100 / 100
 20 ms 4728 KB 
#include <cstdio>
#include <vector>
#include <array>
#include <algorithm>

std::vector<std::array<int,3> > elist;

std::vector<int> edges[1001];
int color[1001];
int sibling_index[1001];
int parent[1001];
int depth[1001];

std::vector<std::array<int,3> > at[1001];

int dp[1001][1<<10];

void dfs_tree(int node){
  for(int i=0;i<edges[node].size();i++){
    int child=edges[node][i];
    edges[child].erase(std::find(edges[child].begin(),edges[child].end(),node));
    color[child]=color[node]^1;
    sibling_index[child]=i;
    parent[child]=node;
    depth[child]=depth[node]+1;
    dfs_tree(child);
  }
}

int lca(int x,int y){
  if(depth[x]<depth[y]) std::swap(x,y);
  while(depth[x]>depth[y]){
    x=parent[x];
  }
  while(x!=y){
    x=parent[x],y=parent[y];
  }
  return x;
}

void update(int node,int mask,int value){
  for(int k=0;k<(1<<edges[node].size());k++){
    if(k&mask) continue;
    dp[node][k|mask]=std::max(dp[node][k|mask],dp[node][k]+value);
  }
}

void dfs_solve(int node){
  for(int i=0;i<edges[node].size();i++){
    int child=edges[node][i];
    dfs_solve(child);
    update(node,1<<i,dp[child][(1<<edges[child].size())-1]);
  }
  for(auto e:at[node]){
    //printf("at %d: %d<=>%d +%d\n",node,e[0],e[1],e[2]);
    int value=0;
    int master=0;
    for(int c=0;c<2;c++){
      int sibling=0;
      for(int x=e[c];x!=node;sibling=1<<sibling_index[x],x=parent[x]){
	value+=dp[x][(1<<edges[x].size())-1-sibling];
      }
      master|=sibling;
    }
    update(node,master,value+e[2]);
  }
  /*
  for(int k=0;k<(1<<edges[node].size());k++){
    printf("%d (%d): %d\n",node,k,dp[node][k]);
  }
  */
}

int main(){
  int N,M;
  scanf("%d %d",&N,&M);
  int total_cost=0;
  for(int i=0;i<M;i++){
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    A--,B--;
    if(C==0){
      edges[A].push_back(B);
      edges[B].push_back(A);
    }else{
      elist.push_back({A,B,C});
      total_cost+=C;
    }
  }
  dfs_tree(0);
  for(auto e:elist){
    if(color[e[0]]==color[e[1]]){
      at[lca(e[0],e[1])].push_back(e);
    }
  }
  dfs_solve(0);
  printf("%d\n",total_cost-dp[0][(1<<edges[0].size())-1]);
}

Compilation message

training.cpp: In function 'void dfs_tree(int)':
training.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<edges[node].size();i++){
               ~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs_solve(int)':
training.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<edges[node].size();i++){
               ~^~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&M);
   ~~~~~^~~~~~~~~~~~~~~
training.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&A,&B,&C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4728 KB Output is correct
2 Correct 15 ms 4600 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 7 ms 1528 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2168 KB Output is correct
2 Correct 8 ms 1176 KB Output is correct
3 Correct 8 ms 1388 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 888 KB Output is correct
2 Correct 6 ms 1656 KB Output is correct
3 Correct 20 ms 4616 KB Output is correct
4 Correct 6 ms 1656 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2168 KB Output is correct
2 Correct 20 ms 4560 KB Output is correct
3 Correct 11 ms 1720 KB Output is correct
4 Correct 8 ms 1400 KB Output is correct