Submission #118208

#	Time	Username	Problem	Language	Result	Execution time	Memory
118208		nvmdava	Tropical Garden (IOI11_garden)	C++17	100 / 100	2979 ms	9188 KiB

garden

#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);
   }

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

   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 && g[j] >= t[i][0]) || (t[i][1] < 0x3f3f3f3f && g[j] >= t[i][1] && (g[j] - t[i][1]) % cyc[1] == 0)) res++;
      }
      answer(res);
   }
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31