Submission #539502

#	Time	Username	Problem	Language	Result	Execution time	Memory
539502		cig32	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1609 ms	522260 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
  bool in[n];
  for(int i=0; i<n; i++) in[i] = 0;
  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]];
    if(i == 5) {
      //for(auto x: cur ) cout << "{" << x.first << ", " << x.second << "} ";
      //cout << "\n";
    }
    for(int j=1; j<adj2[i].size(); j++) { // O(m)
      vector<pair<int, int> > nxt;
      int aptr = 0, bptr = 0;
      //for(int k=0; k<n; k++) cout << in[k];
      //cout << " fgg ";
      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 j=0; j<cur.size(); j++) in[cur[j].second] = 0;
      //if(i == 5) {
      //  cout << "new ";
      //  for(auto x: cur) cout << "{" << x.first << ", " << x.second << "} ";
      //  cout << "\n";
      //}
    }
    //if(i == 5) cout << cur.size() << " yyy\n";
    for(int j=0; j<cur.size(); j++) cur[j].first++, in[cur[j].second] = 0;
    if(cur.size() != block) cur.push_back({0, i});
    optimal[i] = cur;
  }
  /*
  for(int i=0; i<n; i++) {
    cout << "i = " << i << ": ";
    cout << "Adj2[i].size = " <<adj2[i].size() << ", ";
    for(auto x: optimal[i]) cout << "{" << x.first << ", " << x.second << "} ";
    cout << "\n";
  }
  */
  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);
} 

/*
6 5 1
1 6
4 5
5 6
2 6
2 5
6 1 5 
*/

Compilation message (stderr)

bitaro.cpp: In function 'void solve(long long int)':
bitaro.cpp:37: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]
   37 |     for(int j=1; j<adj2[i].size(); j++) { // O(m)
      |                  ~^~~~~~~~~~~~~~~
bitaro.cpp:43: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]
   43 |         while(aptr < cur.size() && in[cur[aptr].second]) aptr++;
      |               ~~~~~^~~~~~~~~~~~
bitaro.cpp:44: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]
   44 |         while(bptr < optimal[adj2[i][j]].size() && in[optimal[adj2[i][j]][bptr].second]) bptr++;
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:45: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]
   45 |         if(aptr == cur.size() && bptr == optimal[adj2[i][j]].size()) break;
      |            ~~~~~^~~~~~~~~~~~~
bitaro.cpp:45: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]
   45 |         if(aptr == cur.size() && bptr == optimal[adj2[i][j]].size()) break;
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:47: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]
   47 |         if(aptr == cur.size()) {
      |            ~~~~~^~~~~~~~~~~~~
bitaro.cpp:51: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]
   51 |         else if(bptr == optimal[adj2[i][j]].size()) {
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:67: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]
   67 |       for(int j=0; j<cur.size(); j++) in[cur[j].second] = 0;
      |                    ~^~~~~~~~~~~
bitaro.cpp:75: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]
   75 |     for(int j=0; j<cur.size(); j++) cur[j].first++, in[cur[j].second] = 0;
      |                  ~^~~~~~~~~~~
bitaro.cpp:76: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]
   76 |     if(cur.size() != block) cur.push_back({0, i});
      |        ~~~~~~~~~~~^~~~~~~~
bitaro.cpp:115: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]
  115 |       for(int i=0; i<optimal[t].size(); i++) {
      |                    ~^~~~~~~~~~~~~~~~~~

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