Submission #370037

#	Time	Username	Problem	Language	Result	Execution time	Memory
370037		retsiger	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1559 ms	415588 KiB

bitaro

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

typedef pair <int, int> ii;

const int maxn = 100100;
const int K = 315;

int N, M, Q;
int dp[maxn];
bool has[maxn];
vector <int> br[maxn];
vector <ii> F[maxn];

vector <ii> merge(vector <ii> &A, vector <ii> &B) {
  vector <ii> ret;
  int l = 0, r = 0, cn = 0;
  while (l < (int)A.size() || r < (int)B.size()) {
    if (l == (int)A.size()) {
      if (!has[B[r].x]) {
        ret.push_back({B[r].x, B[r].y + 1});
        has[B[r].x] = true;
      }
      ++r;
    } else if (r == (int)B.size()) {
      if (!has[A[l].x]) {
        ret.push_back({A[l].x, A[l].y});
        has[A[l].x] = true;
      }
      ++l;
    } else if (A[l].y > B[r].y + 1) {
      if (!has[A[l].x]) {
        ret.push_back({A[l].x, A[l].y});
        has[A[l].x] = true;
      }
      ++l;
    } else {
      if (!has[B[r].x]) {
        ret.push_back({B[r].x, B[r].y + 1});
        has[B[r].x] = true;
      }
      ++r;
    }
    ++cn;
    if (cn == K + 1) break;
  }
  for (auto p : ret) {
    has[p.x] = 0;
  }
  return ret;
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
//  freopen("cc.out", "w", stdout);
  cin >> N >> M >> Q;
  while (M--) {
    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    br[y].push_back(x);
  }
  for (int i = 1; i <= N; ++i) {
    F[i].push_back({i, 0});
    for (int j : br[i]) {
      F[i] = merge(F[i], F[j]);
    }
  }
  while (Q--) {
    int T, Y; cin >> T >> Y;
    vector <int> v;
    for (int i = 1; i <= Y; ++i) {
      int X; cin >> X;
      has[X] = true;
      v.push_back(X);
    }
    if (Y >= K) {
      memset(dp, -0x3f, sizeof dp);
      int re = 0;
      dp[T] = 0;
      if (has[T]) re = -1;
      for (int i = T; i >= 1; --i) {
        for (int j : br[i]) {
          dp[j] = max(dp[j], dp[i] + 1);
          if (has[j]) continue;
          re = max(re, dp[j]);
        }
      }
      cout << re << '\n';
    } else {
      int cn = 0;
      for (auto p : F[T]) {
        if (!has[p.x]) {
          cout << p.y << '\n';
          ++cn;
          break;
        }
      }
      if (!cn) cout << -1 << '\n';
    }
    for (auto X : v) has[X] = false;
  }
}

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