oj.uz

Submission #118202

# Submission time Handle Problem Language Result Execution time Memory
118202 2019-06-18T10:49:43 Z nvmdava Tropical Garden (IOI11_garden) C++17
0 / 100
 46 ms 4088 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

int n, p;
int to[300005];
int best[150005][2];
bool proc[300005][2];
int cyc[2];
int t[300005][2];

void dfs1(int v){
   if(proc[v][0]) return;
   proc[v][0] = 1;
   if(v == p) return;
   dfs1(to[v]);
   t[v][0] = t[to[v]][0] + 1;
}

void dfs0(int v){
   if(proc[v][1]) return;
   proc[v][1] = 1;
   if(v == p + n) return;
   dfs0(to[v]);
   t[v][1] = t[to[v]][1] + 1;
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
   memset(best, -1, sizeof best);
   memset(t, 0x3f, sizeof t);
   for(int i = 0; i < m; i++){
      int v = r[i][0], u = r[i][1];
      if(best[v][0] == -1) best[v][0] = u;
      else if(best[v][1] == -1) best[v][1] = u;
      if(best[u][0] == -1) best[u][0] = v;
      else if(best[u][1] == -1) best[u][1] = v;
   }
   ::n = n;
   ::p = p;
   for(int i = 0; i < n; i++)
      if(best[i][1] == -1) best[i][1] = best[i][0];

   for(int i = 0; i < n; i++){
      to[i] = best[i][0] + n * (best[best[i][0]][0] == i);
      to[i + n] = best[i][1] + n * (best[best[i][1]][0] == i);
   }

   t[p][0] = 0;
   t[p + n][1] = 0;

   for(int i = 0; i < n  * 2; i++){
      dfs1(i);
      dfs0(i);
   }

   for(int i = 0; i < 2 * n; i++){
      cerr<<i<<' '<<to[i]<<'\n';
   }
   cerr<<'\n';

   cyc[0] = 1 + t[to[p]][0];
   cyc[1] = 1 + t[to[n + p]][1];

   for(int i = 0; i < n * 2; i++){
      cerr<<i<<' '<<t[i][0]<<' '<<t[i][1]<<'\n';
   }
   cerr<<cyc[0]<<' '<<cyc[1]<<'\n';

   for(int j = 0; j < q; j++){
      int res = 0;
      for(int i = 0; i < n; i++){
         if((t[i][0] < 0x3f3f3f3f && (g[j] - t[i][0]) % cyc[0] == 0) || (t[i][1] < 0x3f3f3f3f && (g[j] - t[i][1]) % cyc[1] == 0)) res++;
      }
      answer(res);
   }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -