Submission #757486

#	Time	Username	Problem	Language	Result	Execution time	Memory
757486		mgl_diamond	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2072 ms	416084 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;
const int SIZE = 331;

int n, m, q;

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

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

void dfs(int u) {
  if (calc[u]) return;
  calc[u] = 1;

  for(int i=0; i<graph[u].size(); ++i) {
    p[i] = 0;
    dfs(graph[u][i]);
  }

  for(int r=0; r<SIZE; ++r) { 
    int cur = -1;
    for(int i=0; i<graph[u].size(); ++i) {
      int v = graph[u][i];
      while (p[i] < best[v].size() && used[best[v][p[i]].fi]) ++p[i];
      if (p[i] == best[v].size()) continue;
      if (cur ==  -1 || comp(best[v][p[i]], best[graph[u][cur]][p[cur]])) cur = i;
    }
    if (cur == -1) break;
    best[u].emplace_back(best[graph[u][cur]][p[cur]]);
    used[best[graph[u][cur]][p[cur]].fi] = 1;
  }
  if (best[u].size() < SIZE) best[u].emplace_back(u, -1);

  for(auto &v : best[u]) {
    used[v.fi] = 0;
    ++v.se;
  }
}

int dp[N][2];

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

  if (allow[u]) dp[u][1] = 0;

  for(int v : graph[u]) {
    work2(v);

    if (dp[v][0] != -1) 
      dp[u][0] = max(dp[u][0], dp[v][0] + 1);

    if (dp[v][1] != -1)
      dp[u][0] = max(dp[u][0], dp[v][1] + 1);
  }
}

void solve() {
  cin >> n >> m >> q;

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

  for(int i=1; i<=n; ++i) {
    allow[i] = 1;
    dfs(i);
  }

  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][0] = dp[i][1] = -1;
      }
      work2(s);
      cout << max(dp[s][0], dp[s][1]) << "\n";
    }

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

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 'void dfs(int)':
bitaro.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i=0; i<graph[u].size(); ++i) {
      |                ~^~~~~~~~~~~~~~~~
bitaro.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0; i<graph[u].size(); ++i) {
      |                  ~^~~~~~~~~~~~~~~~
bitaro.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |       while (p[i] < best[v].size() && used[best[v][p[i]].fi]) ++p[i];
      |              ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |       if (p[i] == best[v].size()) continue;
      |           ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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