oj.uz

Submission #51618

# Submission time Handle Problem Language Result Execution time Memory
51618 2018-06-19T08:19:16 Z model_code Training (IOI07_training) C++17
100 / 100
 17 ms 4784 KB 
#include <algorithm>
#include <cstdio>
#include <vector>
#include <memory.h>

using namespace std;

#define MAXN 1000
#define MAXK 10

typedef pair<int,int> Pair;

struct Edge {
   int u, v; 
   int cost;
   int LCA; // lowest common ancestor of u and v
} E[MAXN*MAXK/2];

int n, m;
int costSum;
int traversalTime;
int discover[MAXN];
int finish[MAXN];
int depth[MAXN];
int degree[MAXN];
int color[MAXN];
Pair parent[MAXN];
vector<int> treeLinks[MAXN];

int DP[MAXN][1<<MAXK];

void load() {
   costSum = 0;
   scanf( "%d%d", &n, &m );
   for( int i = 0; i < m; ++i ) {
      scanf( "%d%d%d", &E[i].u, &E[i].v, &E[i].cost ); --E[i].u; --E[i].v;
      
      costSum += E[i].cost;
      if( E[i].cost == 0 ) {
         treeLinks[E[i].u].push_back( E[i].v );
         treeLinks[E[i].v].push_back( E[i].u );
      }
   }
}

void treeInit( int a ) {
   discover[a] = ++traversalTime;
   for( vector<int>::iterator it = treeLinks[a].begin(); it != treeLinks[a].end(); ++it ) {
      if( *it == parent[a].first ) continue;
      
      color[*it] = color[a] ^ 1;
      depth[*it] = depth[a] + 1;
      parent[*it] = Pair( a, 1<<degree[a]++ );

      treeInit( *it );
   }
   finish[a] = ++traversalTime;
}

void init() {
   memset( DP, 0, sizeof DP );
   
   traversalTime = 0;
   color[0] = 0;
   depth[0] = 0;
   parent[0] = Pair( -1, -1 );
   treeInit( 0 );
}

void calcLCA() {
   for( int i = 0; i < m; ++i ) {
      int u = E[i].u;
      int v = E[i].v;
      while( depth[u] > depth[v] ) u = parent[u].first;
      while( depth[v] > depth[u] ) v = parent[v].first;
      while( u != v ) { 
         u = parent[u].first;
         v = parent[v].first;
      }
      E[i].LCA = u;
   }
}

bool orderByLCAFinishTime( const Edge &A, const Edge &B ) {
   return finish[A.LCA] < finish[B.LCA];
}

void solve() {
   Pair U, V;
   for( int i = 0; i < m; ++i ) {
      if( E[i].cost != 0 && color[E[i].u] != color[E[i].v] ) continue;

      int L = E[i].LCA;
      int sum = E[i].cost;
      
      for( U = Pair(E[i].u, 0); U.first != L; U = parent[U.first] ) sum += DP[U.first][U.second];
      for( V = Pair(E[i].v, 0); V.first != L; V = parent[V.first] ) sum += DP[V.first][V.second];

      for( int mask = (1<<degree[L])-1; mask >= 0; --mask ) 
         if( !(mask & U.second || mask & V.second) ) 
            DP[L][mask] = max(DP[L][mask], sum + DP[L][mask | U.second | V.second]);
   }
}

int main( void ) {
   load();
   init();
   calcLCA();
   sort( E, E+m, orderByLCAFinishTime );
   solve();
   printf( "%d\n", costSum - DP[0][0] );
   return 0;
}

Compilation message

training.cpp: In function 'void load()':
training.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d%d", &n, &m );
    ~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:36:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( "%d%d%d", &E[i].u, &E[i].v, &E[i].cost ); --E[i].u; --E[i].v;
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4584 KB Output is correct
2 Correct 6 ms 4584 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4588 KB Output is correct
2 Correct 5 ms 4664 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4664 KB Output is correct
2 Correct 6 ms 4664 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4664 KB Output is correct
2 Correct 5 ms 4664 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4696 KB Output is correct
2 Correct 10 ms 4696 KB Output is correct
3 Correct 7 ms 4696 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 7 ms 4696 KB Output is correct
3 Correct 17 ms 4768 KB Output is correct
4 Correct 7 ms 4768 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4768 KB Output is correct
2 Correct 15 ms 4784 KB Output is correct
3 Correct 10 ms 4784 KB Output is correct
4 Correct 9 ms 4784 KB Output is correct