Submission #135837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135837	2019-07-24T12:08:58 Z	model_code	Link (CEOI06_link)	C++17	100 / 100	450 ms	47376 KB

link

#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

#	Verdict	Execution time	Memory	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