Submission #757543

#	Time	Username	Problem	Language	Result	Execution time	Memory
757543		mgl_diamond	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2090 ms	423068 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second

const int N = 1e5+5;
const int INF = 1e9;
int SIZE;

int n, m, q;

bool allow[N], used[N], calc[N];
int p[N], block[N];
vector<ii> best[N];
vector<int> graph[N], adj[N];

bool cmp(ii a, ii b) {
  return a.se > b.se;
}

void prep() {
  for(int i=1; i<=n; ++i) best[i].emplace_back(i, 0);

  for(int i=1; i<=n; ++i)
    for(int x : adj[i]) {
      vector<ii> mer;
      
      int ni = best[i].size(), nx = best[x].size();
      int ci = 0, cx =0 ;

      for(int t=0; t<SIZE; ++t) {
        if (ci == ni && cx == nx) break;

        if (ci == ni) mer.emplace_back(best[x][cx]);
        else if (cx == nx) mer.emplace_back(best[i][ci].fi, best[i][ci].se+1);
        else {
          if (best[i][ci].se+1 > best[x][cx].se) mer.emplace_back(best[i][ci].fi, best[i][ci].se+1);
          else mer.emplace_back(best[x][cx]);
        }

        used[mer.back().fi] = 1;
        while (ci < ni && used[best[i][ci].fi]) ++ci;
        while (cx < nx && used[best[x][cx].fi]) ++cx;
      }

      for(auto &v : mer) {
        used[v.fi] = 0;
      }
      swap(best[x], mer);
    }
}

int dp[N];

void work2(int u) {
  calc[u] = 1;

  for(int v : adj[u]) {
    if (!calc[v]) work2(v);
    if (dp[v] != -1) dp[u] = max(dp[u], dp[v] + 1);
  }
}

void solve() {
  cin >> n >> m >> q;
  SIZE = 331;

  for(int i=0; i<m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    graph[v].push_back(u);
  }

  fill(allow, allow+n+1, 1);
  prep();

  for(int t=0; t<q; ++t) {
    int s, m;
    cin >> s >> m;

    for(int j=0; j<m; ++j) {
      cin >> block[j];
      allow[block[j]] = 0;
    }

    if (s < SIZE) {
      bool found = 0;
      for(auto cand : best[s]) if (allow[cand.fi]) {
        cout << cand.se << "\n";
        found = 1;
        break;
      }
      if (!found) cout << "-1\n";
    }
    else {
      for(int i=1; i<=n; ++i) {
        calc[i] = 0;
        dp[i] = -1;
      }
      dp[s] = 0;
      calc[s] = 1;
      int ans = -1;
      for(int i=1; i<=n; ++i) if (allow[i]) {
        if (!calc[i]) work2(i);
        ans = max(ans, dp[i]);
      }
      cout << ans << "\n";
    }

    for(int j=0; j<m; ++j) {
      allow[block[j]] = 1;
    }
  }

  // for(int i=1; i<=n; ++i) {
  //   cout << "From " << i << " Has " << best[i].size() << " Choices: \n";
  //   for(auto v : best[i]) cout << "Vertice " << v.fi << " Dist " << v.se << "\n";
  //   cout << "------------\n";
  // }
}

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

  if (fopen("input.inp", "r")) {
    freopen("input.inp", "r", stdin);
    freopen("input.out", "w", stdout);
  }

  solve();
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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