Submission #198335

#	Time	Username	Problem	Language	Result	Execution time	Memory
198335		quocnguyen1012	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1543 ms	333600 KiB

bitaro

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
int magic = 205;

vector<int> adj[maxn], radj[maxn];
int N, M, Q;
pair<int, int> dist[maxn][405];
int D[maxn], del[maxn];
bool vis[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> M >> Q;
  while (M--){
    int u, v; cin >> u >> v;
    adj[v].pb(u);
    radj[u].pb(v);
  }
  vector<int> node;
  magic = sqrt(N);
  for (int i = 1; i <= N; ++i){
    for (int j = 1; j <= magic; ++j){
      dist[i][j] = mp(-1, -1);
    }
  }
  for (int u = 1; u <= N; ++u){
    node.clear();
    node.pb(u);
    for (int it : adj[u]){
      for (int k = 1; k <= magic; ++k){
        if (dist[it][k].fi == -1) continue;
        int v = dist[it][k].se;
        D[v] = max(D[v], dist[it][k].fi + 1);
        if (!vis[v]){
          vis[v] = 1;
          node.pb(v);
        }
      }
    }
    sort(node.begin(), node.end(), [&](const int & x, const int & y){
      return D[x] > D[y];
    });
    for (int j = 1; j <= magic && j <= (int)node.size(); ++j){
      dist[u][j] = mp(D[node[j - 1]], node[j - 1]);
    }
    for (auto & v : node)
      D[v] = vis[v] = 0;
  }
  while (Q--){
    int u, n; cin >> u >> n;
    for (int i = 1; i <= n; ++i){
      cin >> del[i];
      vis[del[i]] = true;
    }
    int ret = -2;
    for (int j = 1; j <= magic; ++j){
      if (dist[u][j].fi == -1){
        ret = -1;
        break;
      }
      else if (!vis[dist[u][j].se]){
        ret = dist[u][j].fi;
        break;
      }
    }
    if (ret == -2){
      ret = -1;
      if (!vis[u]) ret = 0;
      for (int i = u - 1; i >= 1; --i){
        D[i] = -1e8;
        for (int v : radj[i]){
          if (v <= u){
            D[i] = max(D[i], D[v] + 1);
          }
        }
        if (!vis[i]){
          ret = max(ret, D[i]);
        }
      }
      for (int i = u; i >= 1; --i){
        D[i] = 0;
      }
    }
    for (int i = 1; i <= n; ++i){
      vis[del[i]] = false;
    }
    cout << ret << '\n';
  }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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