oj.uz

Submission #650043

# Submission time Handle Problem Language Result Execution time Memory
650043 2022-10-12T06:26:42 Z alvinpiter Tropical Garden (IOI11_garden) C++17
100 / 100
 2670 ms 57480 KB 
/*
Let's build another graph by "splitting" each node of the original original graph. A node u in the original graph will
be split to:
* Node u in the new graph. All edges which are not the best edge in the original graph will be directed to this node.
  Also, this node will have 1 outgoing edge to node v where u-v is the best outgoing edge for u in the original graph.
* Node (u + N) in the new graph. The best edge in the original graph will be directed to this node.
  Also, this node will have 1 outgoing edge to node v where u-v is the second-best outgoing edge for u in the original graph.
  If there's no such v, then just use the best edge.

Notice that our new graph will have 2*N vertices. Now we'd like to count the distance from each node to either
node P or P + N in the new graph. There are 3 cases:
* Node P or (P + N) is not reachable
* Node P or (P + N) is only reachable once
* Node P or (P + N) is reachable multiple times, due to being in a cycle

Instead of starting DFS from each node, we will start DFS from P or (P + N) in the reversed graph, hence DFS is only performed
twice. While doing so, we maintain the distance to each other node and the cycle length if any.

We can then answer the queries by checking each of the 3 cases above and also utilizing the distance and cycle length data.

Total complexity is O(NQ).
*/

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 2000000000
#define MAXN 150000

int N;
vector<pair<int, int> > oriAdj[MAXN + 3]; // {beauty, v}
vector<int> adj[2 * MAXN + 3], revAdj[2 * MAXN + 3];
int dist[2 * MAXN + 3][2], cycleLength[2];
bool visited[2 * MAXN + 3][2];

void addEdgeToNewGraph(int u, int v, int beauty) {
  bool isBestForV = (beauty == oriAdj[v][0].first);
  int resolvedV = (isBestForV ? v + N : v);
  adj[u].push_back(resolvedV);
}

void dfs(int u, int t, int step, int origin) {
  dist[u][t] = step;
  visited[u][t] = true;

  for (auto v: revAdj[u]) {
    if (v == origin) {
      cycleLength[t] = step + 1;
    }

    if (!visited[v][t]) {
      dfs(v, t, step + 1, origin);
    }
  }
}

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
  N = n;

  for (int i = 0; i < m; i++) {
    int u = r[i][0], v = r[i][1], beauty = i;
    oriAdj[u].push_back({beauty, v});
    oriAdj[v].push_back({beauty, u});
  }

  for (int u = 0; u < n; u++) {
    sort(oriAdj[u].begin(), oriAdj[u].end());
  }

  for (int u = 0; u < n; u++) {
    // Add directed edge from u to v or (v + n).
    if (true) {
      auto [beauty, v] = oriAdj[u][0];
      addEdgeToNewGraph(u, v, beauty);
    }

    // Add directed edge from (u + n) to v or (v + n).
    if (true) {
      auto [beauty, v] = oriAdj[u].size() > 1 ? oriAdj[u][1] : oriAdj[u][0];
      addEdgeToNewGraph(u + n, v, beauty);
    }
  }

  /*
  Reverse the edges of the new graph.
  This could be done in the previous step, but to make it more understandable, I do it separately.
  */
  for (int u = 0; u < 2 * n; u++) {
    for (auto v: adj[u]) {
      revAdj[v].push_back(u);
    }
  }

  for (int t = 0; t < 2; t++) {
    cycleLength[t] = -1;
    for (int i = 0; i < 2 * n; i++) {
      dist[i][t] = INF;
      visited[i][t] = false;
    }
  }

  dfs(p, 0, 0, p);
  dfs(p + n, 1, 0, p + n);

  for (int query = 0; query < q; query++) {
    int ans = 0;
    for (int u = 0; u < n; u++) {
      bool possible = false;
      for (int t = 0; t < 2; t++) {
        if (dist[u][t] == g[query] || (cycleLength[t] != -1 && g[query] >= dist[u][t] && (g[query] - dist[u][t])%cycleLength[t] == 0)) {
          possible = true;
        }
      }

      if (possible) {
        ans += 1;
      }
    }

    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18024 KB Output is correct
3 Correct 9 ms 18132 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17876 KB Output is correct
6 Correct 10 ms 18320 KB Output is correct
7 Correct 9 ms 17876 KB Output is correct
8 Correct 9 ms 18004 KB Output is correct
9 Correct 12 ms 18340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18024 KB Output is correct
3 Correct 9 ms 18132 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17876 KB Output is correct
6 Correct 10 ms 18320 KB Output is correct
7 Correct 9 ms 17876 KB Output is correct
8 Correct 9 ms 18004 KB Output is correct
9 Correct 12 ms 18340 KB Output is correct
10 Correct 8 ms 17876 KB Output is correct
11 Correct 21 ms 21716 KB Output is correct
12 Correct 37 ms 24448 KB Output is correct
13 Correct 61 ms 46892 KB Output is correct
14 Correct 145 ms 39812 KB Output is correct
15 Correct 159 ms 40140 KB Output is correct
16 Correct 115 ms 34344 KB Output is correct
17 Correct 129 ms 32180 KB Output is correct
18 Correct 42 ms 24456 KB Output is correct
19 Correct 144 ms 39808 KB Output is correct
20 Correct 153 ms 40344 KB Output is correct
21 Correct 157 ms 34176 KB Output is correct
22 Correct 153 ms 32132 KB Output is correct
23 Correct 161 ms 42080 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18132 KB Output is correct
2 Correct 10 ms 18024 KB Output is correct
3 Correct 9 ms 18132 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 17876 KB Output is correct
6 Correct 10 ms 18320 KB Output is correct
7 Correct 9 ms 17876 KB Output is correct
8 Correct 9 ms 18004 KB Output is correct
9 Correct 12 ms 18340 KB Output is correct
10 Correct 8 ms 17876 KB Output is correct
11 Correct 21 ms 21716 KB Output is correct
12 Correct 37 ms 24448 KB Output is correct
13 Correct 61 ms 46892 KB Output is correct
14 Correct 145 ms 39812 KB Output is correct
15 Correct 159 ms 40140 KB Output is correct
16 Correct 115 ms 34344 KB Output is correct
17 Correct 129 ms 32180 KB Output is correct
18 Correct 42 ms 24456 KB Output is correct
19 Correct 144 ms 39808 KB Output is correct
20 Correct 153 ms 40344 KB Output is correct
21 Correct 157 ms 34176 KB Output is correct
22 Correct 153 ms 32132 KB Output is correct
23 Correct 161 ms 42080 KB Output is correct
24 Correct 10 ms 17876 KB Output is correct
25 Correct 104 ms 21824 KB Output is correct
26 Correct 150 ms 24468 KB Output is correct
27 Correct 2291 ms 46928 KB Output is correct
28 Correct 930 ms 39852 KB Output is correct
29 Correct 2658 ms 40244 KB Output is correct
30 Correct 1500 ms 34356 KB Output is correct
31 Correct 1617 ms 32204 KB Output is correct
32 Correct 164 ms 24472 KB Output is correct
33 Correct 997 ms 39856 KB Output is correct
34 Correct 2670 ms 40264 KB Output is correct
35 Correct 1589 ms 34124 KB Output is correct
36 Correct 1505 ms 32236 KB Output is correct
37 Correct 708 ms 42112 KB Output is correct
38 Correct 2012 ms 57480 KB Output is correct