oj.uz

Submission #650025

# Submission time Handle Problem Language Result Execution time Memory
650025 2022-10-12T01:15:06 Z alvinpiter Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 57948 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 150000
#define MAXE 300000
#define MAXLG 30

struct DirectedEdge {
  int id, from, to, beauty;
  DirectedEdge(int id_, int from_, int to_, int beauty_): id(id_), from(from_), to(to_), beauty(beauty_) {}
  bool operator<(DirectedEdge other) const {
    return beauty < other.beauty;
  }
};

vector<DirectedEdge> directedEdges, goingOutEdges[MAXN + 3];
int nxt[MAXE + 3][MAXLG + 3];

void count_routes(int n, int m, int p, int r[][2], int q, int g[]) {
  int numberOfDirectedEdges = 0;
  for (int i = 0; i < m; i++) {
    int u = r[i][0], v = r[i][1], beauty = i;

    DirectedEdge uvEdge = DirectedEdge(numberOfDirectedEdges++, u, v, beauty);
    DirectedEdge vuEdge = DirectedEdge(numberOfDirectedEdges++, v, u, beauty);

    directedEdges.push_back(uvEdge);
    goingOutEdges[u].push_back(uvEdge);

    directedEdges.push_back(vuEdge);
    goingOutEdges[v].push_back(vuEdge);
  }

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

  // cout << "\ngoingOutEdges\n";
  // for (int i = 0; i < n; i++) {
  //   cout << i << ":";
  //   for (auto edge: goingOutEdges[i]) {
  //     cout << " (" << edge.id << ", " << edge.from << ", " << edge.to << ", " << edge.beauty << ")";
  //   }
  //   cout << endl;
  // }

  for (auto directedEdge: directedEdges) {
    int firstEdgeId = directedEdge.id;
    int secondEdgeId;

    if (goingOutEdges[directedEdge.to].size() == 1) {
      secondEdgeId = goingOutEdges[directedEdge.to][0].id;
    } else {
      for (auto goingOutEdge: goingOutEdges[directedEdge.to]) {
        if (goingOutEdge.beauty != directedEdge.beauty) {
          secondEdgeId = goingOutEdge.id;
          break;
        }
      }
    }

    nxt[firstEdgeId][0] = secondEdgeId;
  }

  // cout << "\nnxt\n";
  // for (int i = 0; i < numberOfDirectedEdges; i++) {
  //   cout << i << ": " << nxt[i][0] << endl;
  // }

  for (int lg = 1; lg <= MAXLG; lg++) {
    for (int i = 0; i < numberOfDirectedEdges; i++) {
      nxt[i][lg] = nxt[nxt[i][lg - 1]][lg - 1];
    }
  }

  for (int i = 0; i < q; i++) {
    int ans = 0;
    for (int startingNode = 0; startingNode < n; startingNode++) {
      int currentEdgeId = goingOutEdges[startingNode][0].id;

      // Jump (g[i] - 1) times
      int numJumps = g[i] - 1;
      for (int lg = 0; lg <= MAXLG; lg++) {
        if (numJumps & (1 << lg)) {
          currentEdgeId = nxt[currentEdgeId][lg];
        }
      }

      if (directedEdges[currentEdgeId].to == p) {
        ans += 1;
      }
    }

    answer(ans);
  }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:63:25: warning: 'secondEdgeId' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     nxt[firstEdgeId][0] = secondEdgeId;
      |     ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4052 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4564 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 4096 KB Output is correct
9 Correct 6 ms 6608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4052 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4564 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 4096 KB Output is correct
9 Correct 6 ms 6608 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 20 ms 11756 KB Output is correct
12 Correct 62 ms 22900 KB Output is correct
13 Correct 143 ms 34188 KB Output is correct
14 Correct 193 ms 55316 KB Output is correct
15 Correct 181 ms 57616 KB Output is correct
16 Correct 186 ms 53444 KB Output is correct
17 Correct 188 ms 53388 KB Output is correct
18 Correct 77 ms 22804 KB Output is correct
19 Correct 220 ms 55252 KB Output is correct
20 Correct 182 ms 57444 KB Output is correct
21 Correct 204 ms 53124 KB Output is correct
22 Correct 186 ms 53180 KB Output is correct
23 Correct 214 ms 57948 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4052 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 4 ms 4564 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 3 ms 4096 KB Output is correct
9 Correct 6 ms 6608 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 20 ms 11756 KB Output is correct
12 Correct 62 ms 22900 KB Output is correct
13 Correct 143 ms 34188 KB Output is correct
14 Correct 193 ms 55316 KB Output is correct
15 Correct 181 ms 57616 KB Output is correct
16 Correct 186 ms 53444 KB Output is correct
17 Correct 188 ms 53388 KB Output is correct
18 Correct 77 ms 22804 KB Output is correct
19 Correct 220 ms 55252 KB Output is correct
20 Correct 182 ms 57444 KB Output is correct
21 Correct 204 ms 53124 KB Output is correct
22 Correct 186 ms 53180 KB Output is correct
23 Correct 214 ms 57948 KB Output is correct
24 Correct 11 ms 3908 KB Output is correct
25 Execution timed out 5015 ms 12012 KB Time limit exceeded
26 Halted 0 ms 0 KB -