Submission #539482

#	Time	Username	Problem	Language	Result	Execution time	Memory
539482		cig32	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2023 ms	155828 KiB

bitaro

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> adj[MAXN];
vector<int> adj2[MAXN];

void solve(int tc) {
  int n, m, q;
  cin >> n >> m >> q;
  for(int i=0; i<m; i++) {
    int s,e;
    cin >> s >> e;
    s--, e--;
    adj2[e].push_back(s); adj[s].push_back(e);
  }
  int block = ceil(sqrt(n));
  vector<pair<int, int> > optimal[n]; // best, second best, etc
  for(int i=0; i<n; i++) {
    if(adj2[i].empty()) {
      optimal[i].push_back({0, i});
      continue;
    }
    vector<pair<int, int> > cur = optimal[adj2[i][0]];
    for(int j=1; j<adj2[i].size(); j++) { // O(m)
      vector<pair<int, int> > nxt;
      unordered_map<int, bool> in;
      int aptr = 0, bptr = 0;
      for(int k=0; k<block; k++) {
        while(aptr < cur.size() && in[cur[aptr].second]) aptr++;
        while(bptr < optimal[adj2[i][j]].size() && in[optimal[adj2[i][j]][bptr].second]) bptr++;
        if(aptr == cur.size() && bptr == optimal[adj2[i][j]].size()) break;

        if(aptr == cur.size()) {
          in[optimal[adj2[i][j]][bptr].second] = 1;
          nxt.push_back(optimal[adj2[i][j]][bptr++]);
        }
        else if(bptr == optimal[adj2[i][j]].size()) {
          in[cur[aptr].second] = 1;
          nxt.push_back(cur[aptr++]);
        }
        else {
          if(optimal[adj2[i][j]][bptr] > cur[aptr]) {
            in[optimal[adj2[i][j]][bptr].second] = 1;
            nxt.push_back(optimal[adj2[i][j]][bptr++]);
          }
          else {
            in[cur[aptr].second] = 1;
            nxt.push_back(cur[aptr++]);
          }
        }
      }
      cur = nxt;
    }
    for(int i=0; i<cur.size(); i++) cur[i].first++;
    if(cur.size() != block) cur.push_back({0, i});
    optimal[i] = cur;
  }
  bool blocked[n];
  for(int i=0; i<n; i++) blocked[i] = 0;
  while(q--) {
    int t, y;
    cin >> t >> y;
    t--;
    vector<int> a(y);
    for(int j=0; j<y; j++) {
      cin >> a[j];
      a[j]--;
    }
    for(int i=0; i<y; i++) blocked[a[i]] = 1;
    if(y >= block) {
      int ans = -1;
      int dp[t+1];
      dp[t] = 0;
      if(!blocked[t]) ans = 0;
      for(int i=t-1; i>=0; i--) {
        dp[i] = -1;
        for(int x: adj[i]) {
          if(x <= t && dp[x] != -1) dp[i] = max(dp[i], dp[x] + 1);
        }
        if(!blocked[i]) ans = max(ans, dp[i]);
      }
      cout << ans << '\n';
    }
    else {
      int ans = -1;
      for(int i=0; i<optimal[t].size(); i++) {
        if(!blocked[optimal[t][i].second]) {
          ans = optimal[t][i].first;
          break;
        }
      }
      cout << ans << "\n";
    }
    for(int i=0; i<y; i++) blocked[a[i]] = 0;
  }
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

/*
12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8
*/

Compilation message (stderr)

bitaro.cpp: In function 'void solve(long long int)':
bitaro.cpp:31:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int j=1; j<adj2[i].size(); j++) { // O(m)
      |                  ~^~~~~~~~~~~~~~~
bitaro.cpp:36:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(aptr < cur.size() && in[cur[aptr].second]) aptr++;
      |               ~~~~~^~~~~~~~~~~~
bitaro.cpp:37:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while(bptr < optimal[adj2[i][j]].size() && in[optimal[adj2[i][j]][bptr].second]) bptr++;
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:38:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(aptr == cur.size() && bptr == optimal[adj2[i][j]].size()) break;
      |            ~~~~~^~~~~~~~~~~~~
bitaro.cpp:38:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(aptr == cur.size() && bptr == optimal[adj2[i][j]].size()) break;
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if(aptr == cur.size()) {
      |            ~~~~~^~~~~~~~~~~~~
bitaro.cpp:44:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         else if(bptr == optimal[adj2[i][j]].size()) {
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0; i<cur.size(); i++) cur[i].first++;
      |                  ~^~~~~~~~~~~
bitaro.cpp:62:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   62 |     if(cur.size() != block) cur.push_back({0, i});
      |        ~~~~~~~~~~~^~~~~~~~
bitaro.cpp:93:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       for(int i=0; i<optimal[t].size(); i++) {
      |                    ~^~~~~~~~~~~~~~~~~~

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