제출 #118191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
118191		nvmdava	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	0 / 100	6 ms	4188 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];
bool in[300005];

void dfs1(int v){
   if(proc[v][0]) return;
   proc[v][0] = 1;
   if(v == p) return;
   dfs1(to[v]);
   if(t[to[v]][0] == -1) t[v][0] = -1;
   else 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]);
   if(t[to[v]][1] == -1) t[v][1] = -1;
   else 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, -1, 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; i++){
      dfs1(i);
      dfs0(i);
   }

   for(int j = 0 ; j < 2; j++){
      memset(in, 0, sizeof in);
      int v = to[p + j * n];
      cyc[j] = 1;
      while(v != p + j * n){
         in[v] = 1;
         cyc[j]++;
         v = to[v];
         if(in[v] == 1){
            cyc[j] = 1000000001;
            break;
         }
      }
   }
   for(int j = 0; j < q; j++){
      int res = 0;
      for(int i = 0; i < n; i++){
         if((g[j] - t[i][0]) % cyc[0] == 0 || (g[j] - t[i][1]) % cyc[1] == 0) res++;
      }
      answer(res);
   }
}

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