oj.uz

Submission #1041987

# Submission time Handle Problem Language Result Execution time Memory
1041987 2024-08-02T11:45:21 Z vjudge1 Tropical Garden (IOI11_garden) C++17
49 / 100
 246 ms 71924 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

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 = idx.size();
  nodes.clear();

  cerr << "siz " << siz << endl;

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

  for (int j = 1; j <= J; ++j) {
    for (int u = 0; u < siz; ++u) {
      succ[j][u] = succ[j-1][ succ[j-1][u] ];
    }
  }

  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 j = J; j >= 0; --j) {
        if (K & (1 << j)) u = succ[j][u];
      }

      auto node = inv[u];
      if (node.second == P) ++cnt;
    }

    cerr << cnt << endl;
    answer(cnt);
  }




  // 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 1 ms 856 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1116 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 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 12 ms 4956 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1116 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 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 12 ms 4956 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 57 ms 21028 KB Output is correct
12 Correct 138 ms 41040 KB Output is correct
13 Incorrect 246 ms 71924 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1116 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 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 12 ms 4956 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 57 ms 21028 KB Output is correct
12 Correct 138 ms 41040 KB Output is correct
13 Incorrect 246 ms 71924 KB Output isn't correct
14 Halted 0 ms 0 KB -