oj.uz

답안 #1041987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -