Submission #118212

#	Time	Username	Problem	Language	Result	Execution time	Memory
118212		nvmdava	Tropical Garden (IOI11_garden)	C++17	0 / 100	11 ms	7728 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 dfs(int v, int k){
   if(proc[v][k]) return;
   proc[v][k] = 1;
   if(v == p + k * n) return;
   dfs(to[v], k);
   t[v][k] = t[to[v]][k] + 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++){
      dfs(i, 1);
      dfs(i, 0);
   }
   for(int j = 0; j < q; j++){
      int res = 0;
      for(int i = 0; i < n; i++){
         if((t[i][0] < t[n*2][0] && (g[j] - t[i][0]) % cyc[0] == 0 && g[j] >= t[i][0]) || (t[i][1] < t[n*2][0] && g[j] >= t[i][1] && (g[j] - t[i][1]) % cyc[1] == 0)) res++;
      }
      answer(res);
   }
}

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