Submission #134055

#	Time	Username	Problem	Language	Result	Execution time	Memory
134055		dragonslayerit	Training (IOI07_training)	C++14	100 / 100	20 ms	4728 KiB

training

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

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