oj.uz

Submission #445078

# Submission time Handle Problem Language Result Execution time Memory
445078 2021-07-16T11:16:41 Z prvocislo Tropical Garden (IOI11_garden) C++17
100 / 100
 2739 ms 34644 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.5e5 + 5, inf = 2e9 + 5;
struct ans { int a, b; ans(int A = inf-1, int B = inf):a(A), b(B) {} };
int d[2][maxn*2], len[2], cnt[maxn * 2];
vector<int> g[maxn*2];
void dfs(int u, int i)
{
  for (int v : g[u])
  {
    if (d[i][v] != inf)
    {
      if (d[i][v] == 0) len[i] = d[i][u] + 1;
      continue;
    }
    d[i][v] = d[i][u] + 1;
    dfs(v, i);
  }
}
void count_routes(int n, int m, int p, int e[][2], int q, int qu[])
{
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < 2; j++)
    {
      int u = e[i][j], v = e[i][j^1];
      if (cnt[u] < 2) g[v + (cnt[v] == 0) * n].push_back(u + cnt[u] * n);
    }
    for (int j = 0; j < 2; j++) cnt[e[i][j]]++;
  }
  for (int i = 0; i < n; i++)
  {
    if (cnt[i] >= 2) continue;
    for (int j : g[i+n]) g[i].push_back(j);
    g[i+n].clear();
  }
  for (int l = 0; l < 2; l++)
  {
    fill(d[l], d[l] + maxn * 2, inf); len[l] = inf;
    d[l][l*n+p] = 0;
    dfs(l*n+p, l);
  }
  for (int i = 0; i < q; i++)
  {
    int cnt = 0;
    for (int j = 0; j < n; j++)
    {
      bool ok = false;
      for (int l = 0; l < 2; l++) 
        if (d[l][j] <= qu[i] && (qu[i] - d[l][j]) % len[l] == 0) ok = true; 
      cnt += ok;
    }
    answer(cnt);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9788 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9932 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9788 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9932 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct
10 Correct 7 ms 9640 KB Output is correct
11 Correct 14 ms 11212 KB Output is correct
12 Correct 25 ms 12312 KB Output is correct
13 Correct 53 ms 30220 KB Output is correct
14 Correct 81 ms 18232 KB Output is correct
15 Correct 113 ms 18496 KB Output is correct
16 Correct 86 ms 16492 KB Output is correct
17 Correct 75 ms 15540 KB Output is correct
18 Correct 26 ms 12288 KB Output is correct
19 Correct 83 ms 18344 KB Output is correct
20 Correct 119 ms 18628 KB Output is correct
21 Correct 89 ms 16208 KB Output is correct
22 Correct 82 ms 15504 KB Output is correct
23 Correct 81 ms 19220 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9788 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9932 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9676 KB Output is correct
9 Correct 8 ms 9804 KB Output is correct
10 Correct 7 ms 9640 KB Output is correct
11 Correct 14 ms 11212 KB Output is correct
12 Correct 25 ms 12312 KB Output is correct
13 Correct 53 ms 30220 KB Output is correct
14 Correct 81 ms 18232 KB Output is correct
15 Correct 113 ms 18496 KB Output is correct
16 Correct 86 ms 16492 KB Output is correct
17 Correct 75 ms 15540 KB Output is correct
18 Correct 26 ms 12288 KB Output is correct
19 Correct 83 ms 18344 KB Output is correct
20 Correct 119 ms 18628 KB Output is correct
21 Correct 89 ms 16208 KB Output is correct
22 Correct 82 ms 15504 KB Output is correct
23 Correct 81 ms 19220 KB Output is correct
24 Correct 7 ms 9688 KB Output is correct
25 Correct 118 ms 11312 KB Output is correct
26 Correct 163 ms 12240 KB Output is correct
27 Correct 2506 ms 30372 KB Output is correct
28 Correct 923 ms 18392 KB Output is correct
29 Correct 2739 ms 18648 KB Output is correct
30 Correct 1582 ms 16452 KB Output is correct
31 Correct 1597 ms 15684 KB Output is correct
32 Correct 166 ms 12236 KB Output is correct
33 Correct 939 ms 18384 KB Output is correct
34 Correct 2734 ms 18560 KB Output is correct
35 Correct 1727 ms 16404 KB Output is correct
36 Correct 1863 ms 15592 KB Output is correct
37 Correct 783 ms 19360 KB Output is correct
38 Correct 2278 ms 34644 KB Output is correct