Submission #583075

#	Time	Username	Problem	Language	Result	Execution time	Memory
583075		AlexLuchianov	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	616 ms	183316 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

int const nmax = 100000;
int const threshold = 220;
std::vector<int> g[5 + nmax];

int cap[5 + nmax];
std::pair<int, int> dp[5 + nmax][5 + threshold];
std::pair<int,int> aux[5 + threshold * 2];

namespace lowmap{
  int frec[5 + nmax];
  int timestamp = 1;
  void reset() {
    ++timestamp;
  }
  bool find(int val) {
    return frec[val] == timestamp;
  }
  void insert(int val) {
    frec[val] = timestamp;
  }
};

int dpBrut[5 + nmax];

int brute(int target) {
  for(int i = 1;i <= target; i++) {
    if(lowmap::find(i) == 0)
      dpBrut[i] = 1;
    else
      dpBrut[i] = 0;
    for(int h = 0; h < g[i].size(); h++) {
      int to = g[i][h];
      if(0 < dpBrut[to])
        dpBrut[i] = std::max(dpBrut[i], dpBrut[to] + 1);
    }
  }
  return dpBrut[target] - 1;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;
  for(int i = 1;i <= m; i++) {
    int x, y;
    std::cin >> x >> y;
    g[y].push_back(x);
  }
  for(int i = 1;i <= n; i++) {
    cap[i] = 1;
    dp[i][1] = {0, i};
    for(int h = 0; h < g[i].size(); h++) {
      int to = g[i][h];
      std::merge(dp[i] + 1, dp[i] + cap[i] + 1, 
                 dp[to] + 1, dp[to] + cap[to] + 1,
                 aux + 1, std::greater<std::pair<int,int>>() );
      lowmap::reset();
      int lim = cap[i] + cap[to];
      cap[i] = 0;
      for(int j = 1;j <= lim && cap[i] < threshold; j++) {
        if(lowmap::find(aux[j].second) == 0) {
          lowmap::insert(aux[j].second);
          dp[i][++cap[i]] = aux[j];
        }
      }
    }
    for(int j = 1;j <= cap[i]; j++)
      dp[i][j].first++;
  }

  for(int i = 1;i <= q; i++) {
    int x, k;
    std::cin >> x >> k;
    lowmap::reset();
    for(int j = 1;j <= k; j++) {
      int val;
      std::cin >> val;
      lowmap::insert(val);
    }
    if(k < threshold) {
      bool solved = false;
      for(int j = 1; j <= cap[x]; j++)
        if(lowmap::find(dp[x][j].second) == 0) {
          std::cout << dp[x][j].first -1 << '\n';
          solved = true;
          break;
        }
      if(solved == false)
        std::cout << -1 << '\n'; 
    } else {
      std::cout << brute(x) << '\n';
    }
  }
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int brute(int)':
bitaro.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int h = 0; h < g[i].size(); h++) {
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86