oj.uz

답안 #118188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118188 2019-06-18T10:28:12 Z nvmdava 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 5 ms 4216 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];
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;
         }
      }
   }
   int res = 0;
   for(int i = 0; i < n; i++){
      if((g[0] - t[i][0]) % cyc[0] == 0 || (g[0] - t[i][1]) % cyc[1] == 0) res++;
   }
   answer(res);
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -