Submission #757514

#	Time	Username	Problem	Language	Result	Execution time	Memory
757514		mgl_diamond	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	12 ms	14804 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 dfs(int u) {
  calc[u] = 1;

  for(int i=0; i<graph[u].size(); ++i) {
    int v = graph[u][i];
    if (!calc[v])
    dfs(v);

    int x = best[u].size(), y = best[v].size();
    best[u].resize(x + y);
    merge(all(best[u]), all(best[v]), best[u].begin(), cmp);
    if (best[u].size() > SIZE) best[u].resize(SIZE);
  }

  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];

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 = sqrt(n);

  for(int i=0; i<m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(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] = -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;
    }
  }
}

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:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0; i<graph[u].size(); ++i) {
      |                ~^~~~~~~~~~~~~~~~
bitaro.cpp:39:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     if (best[u].size() > SIZE) best[u].resize(SIZE);
      |         ~~~~~~~~~~~~~~~^~~~~~
bitaro.cpp:42:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |   if (best[u].size() < SIZE) best[u].emplace_back(u, -1);
      |       ~~~~~~~~~~~~~~~^~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:121:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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