Submission #1041995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041995		vjudge1	Tropical Garden (IOI11_garden)	C++17	49 / 100	196 ms	55336 KiB

garden

#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});
  }

  int siz = nodes.size();
  
  vector<bool> inP(siz, false);
  map<pair<int,int>,int> idx;
  int idx_ = 0;
  for (auto node : nodes) {
    idx[node] = idx_;
    if (node.second == P) inP[idx_] = true;
    ++idx_;
  }
  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];
      }

      if (inP[u]) ++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 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31