oj.uz

Submission #1041952

# Submission time Handle Problem Language Result Execution time Memory
1041952 2024-08-02T10:46:27 Z vjudge1 Tropical Garden (IOI11_garden) C++17
49 / 100
 5000 ms 16456 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

struct Edge {
  int u, v;

  Edge() {}
  Edge(int u_, int v_) : u(u_), v(v_) {}
};

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  vector<vector<int>> adj(N);
  for (int i = 0; i < M; ++i) {
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }

  set<pair<int,int>> nodes;

  for (int i = 0; i < N; ++i) {
    nodes.insert({-1, i});
    for (int v : adj[i]) nodes.insert({i, v});
  }

  map<pair<int,int>,int> idx;
  map<int,pair<int,int>> inv;
  int idx_ = 0;
  for (auto node : nodes) {
    idx[node] = idx_;
    inv[idx_] = node;
    ++idx_;
  }

  int siz = nodes.size();
  vector<int> succ(siz, -1);
  for (int i = 0; i < N; ++i) {
    succ[idx[{-1, i}]] = idx[{i, adj[i][0]}];
    for (int v : adj[i]) {
      if (v != adj[i][0])
        succ[idx[{v, i}]] = idx[{i, adj[i][0]}];
      else
        succ[idx[{v, i}]] = idx[{i, adj[i][1]}];
    }
  }

  for(int it = 0; it < Q; ++it) {
    int K = G[it];
    int cnt = 0;

    for (int i = 0; i < N; ++i) {
      int u = idx[{-1, i}];
      for (int it2 = 0; it2 < K; ++it2) u = succ[u];
      auto node = inv[u];
      if (node.second == P) ++cnt;
    }

    answer(cnt);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1008 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 13 ms 3696 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1008 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 13 ms 3696 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Execution timed out 5094 ms 16456 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1008 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 13 ms 3696 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Execution timed out 5094 ms 16456 KB Time limit exceeded
12 Halted 0 ms 0 KB -