oj.uz

답안 #135837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135837 2019-07-24T12:08:58 Z model_code Link (CEOI06_link) C++17
100 / 100
 450 ms 47376 KB 
#include <cstdio>
#include <vector>

using namespace std;

#ifdef DJGPP
unsigned _stklen = 16*1024*1024;
#endif

#define MAXN 1000000
const int inf = 1000000000;

int n, k;
int link[MAXN];
int dead[MAXN];
vector<int> adj[MAXN];

vector< vector<int> > ciklusi;

int result = 0;

void nadji_cikluse() {
   vector<int> bio( n, 0 );
   int time = 0;

   for( int i = 0; i < n; ++i ) {
      if( bio[i] ) continue;
      int a, b;

      bio[i] = ++time;
      for( a = link[i]; !bio[a]; a = link[a] )
         bio[a] = ++time;

      if( bio[a] < bio[i] ) continue;

      ciklusi.push_back( vector<int> (1,a) );
      for( b = link[a]; b != a; b = link[b] )
         ciklusi.back().push_back( b );
   }
}

int rec( int a ) {
   int kill = 0;
   for( vector<int>::iterator it = adj[a].begin(); it != adj[a].end(); ++it )
      kill = std::max(kill, rec( *it ));
   if( a == 0 ) kill = k+1;

   dead[a] = 1;
   if( kill == 0 ) {
      kill = k;
      ++result;
   }
   return kill-1;
}

int main( void ) {
   scanf( "%d%d", &n, &k );

   for( int i = 0; i < n; ++i ) {
      int a, b;
      scanf( "%d%d", &a, &b ); --a; --b;
      link[a] = b;
      adj[b].push_back( a );
   }

   nadji_cikluse();

   for( vector< vector<int> >::iterator it = ciklusi.begin(); it != ciklusi.end(); ++it ) {
      vector<int> &ciklus = *it;

      int m = ciklus.size();

      {
         int kill = 0;
         int prev = ciklus[m-1];
         for( int i = 0; i < 2*m; ++i ) {
            int curr = ciklus[i%m];

            if( i < m ) {
               for( vector<int>::iterator it = adj[curr].begin(); it != adj[curr].end(); ++it ) {
                  if( *it == prev ) continue;
                  kill = std::max(kill, rec( *it ));
               }
               if( curr == 0 ) kill = k+1;
            }
            if( kill-- > 0 ) dead[curr] = 1;

            prev = curr;
         }
      }

      vector<int> next( m, inf );

      {
         int prev = 0;
         for( int i = 2*m-1; i >= 0; --i ) {
            int curr = i%m;

            next[curr] = next[prev]+1;
            if( !dead[ciklus[curr]] ) next[curr] = 0;

            prev = curr;
         }
      }
      if( next[0] >= inf ) continue;


      {
         int best = 1000000;
         for( int start = 0; start < k && start < m; ++start ) {
            int cost = 0;
            int i = start + next[start];
            while( i - start < m ) {
               ++cost;
               i += k;
               i += next[i%m];
            }
            best = std::min(best, cost);
         }
         result += best;
      }
   }

   printf( "%d\n", result );

   return 0;
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d%d", &n, &k );
    ~~~~~^~~~~~~~~~~~~~~~~~
link.cpp:61:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf( "%d%d", &a, &b ); --a; --b;
       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 23768 KB Output is correct
2 Correct 23 ms 23804 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 26 ms 24028 KB Output is correct
6 Correct 40 ms 25336 KB Output is correct
7 Correct 65 ms 25896 KB Output is correct
8 Correct 66 ms 26852 KB Output is correct
9 Correct 90 ms 29640 KB Output is correct
10 Correct 83 ms 28132 KB Output is correct
11 Correct 123 ms 31628 KB Output is correct
12 Correct 181 ms 32276 KB Output is correct
13 Correct 214 ms 36640 KB Output is correct
14 Correct 272 ms 36056 KB Output is correct
15 Correct 335 ms 40056 KB Output is correct
16 Correct 362 ms 40400 KB Output is correct
17 Correct 377 ms 43784 KB Output is correct
18 Correct 441 ms 44444 KB Output is correct
19 Correct 437 ms 44876 KB Output is correct
20 Correct 436 ms 46392 KB Output is correct
21 Correct 432 ms 47376 KB Output is correct
22 Correct 438 ms 46412 KB Output is correct
23 Correct 450 ms 45640 KB Output is correct
24 Correct 433 ms 46268 KB Output is correct
25 Correct 427 ms 45936 KB Output is correct