oj.uz

답안 #118209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118209 2019-06-18T11:06:16 Z nvmdava 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
100 / 100
 2959 ms 9196 KB 
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("Ofast")
#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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 7 ms 3948 KB Output is correct
7 Correct 0 ms 3832 KB Output is correct
8 Correct 5 ms 3932 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 7 ms 3948 KB Output is correct
7 Correct 0 ms 3832 KB Output is correct
8 Correct 5 ms 3932 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct
10 Correct 5 ms 3892 KB Output is correct
11 Correct 11 ms 4344 KB Output is correct
12 Correct 20 ms 4728 KB Output is correct
13 Correct 33 ms 8288 KB Output is correct
14 Correct 66 ms 6492 KB Output is correct
15 Correct 51 ms 6620 KB Output is correct
16 Correct 45 ms 6008 KB Output is correct
17 Correct 44 ms 5752 KB Output is correct
18 Correct 20 ms 4700 KB Output is correct
19 Correct 49 ms 6520 KB Output is correct
20 Correct 51 ms 6648 KB Output is correct
21 Correct 46 ms 6008 KB Output is correct
22 Correct 46 ms 5888 KB Output is correct
23 Correct 51 ms 6808 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3832 KB Output is correct
2 Correct 5 ms 3960 KB Output is correct
3 Correct 5 ms 3960 KB Output is correct
4 Correct 5 ms 3832 KB Output is correct
5 Correct 5 ms 3832 KB Output is correct
6 Correct 7 ms 3948 KB Output is correct
7 Correct 0 ms 3832 KB Output is correct
8 Correct 5 ms 3932 KB Output is correct
9 Correct 5 ms 3932 KB Output is correct
10 Correct 5 ms 3892 KB Output is correct
11 Correct 11 ms 4344 KB Output is correct
12 Correct 20 ms 4728 KB Output is correct
13 Correct 33 ms 8288 KB Output is correct
14 Correct 66 ms 6492 KB Output is correct
15 Correct 51 ms 6620 KB Output is correct
16 Correct 45 ms 6008 KB Output is correct
17 Correct 44 ms 5752 KB Output is correct
18 Correct 20 ms 4700 KB Output is correct
19 Correct 49 ms 6520 KB Output is correct
20 Correct 51 ms 6648 KB Output is correct
21 Correct 46 ms 6008 KB Output is correct
22 Correct 46 ms 5888 KB Output is correct
23 Correct 51 ms 6808 KB Output is correct
24 Correct 6 ms 3836 KB Output is correct
25 Correct 112 ms 4444 KB Output is correct
26 Correct 145 ms 4856 KB Output is correct
27 Correct 1529 ms 8272 KB Output is correct
28 Correct 1394 ms 6616 KB Output is correct
29 Correct 1905 ms 6692 KB Output is correct
30 Correct 1074 ms 6100 KB Output is correct
31 Correct 1144 ms 5884 KB Output is correct
32 Correct 169 ms 4776 KB Output is correct
33 Correct 1406 ms 6616 KB Output is correct
34 Correct 1811 ms 6692 KB Output is correct
35 Correct 1020 ms 6060 KB Output is correct
36 Correct 1901 ms 5752 KB Output is correct
37 Correct 925 ms 6916 KB Output is correct
38 Correct 2959 ms 9196 KB Output is correct