Submission #757571

#	Time	Username	Problem	Language	Result	Execution time	Memory
757571		mgl_diamond	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1693 ms	417304 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];
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;
  }
 
  for(auto v : graph[u]) if (!used[v]) {
    if (best[u].size() < SIZE) best[u].emplace_back(v, 0);
  }
  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;
 
    vector<int> block;
 
    for(int j=0; j<m; ++j) {
      int x; cin >> x;
      block.push_back(x);
      allow[x] = 0;
    }
 
    if (m < 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 x : block) {
      allow[x] = 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);
  }
 
  if (fopen("balancing.in", "r")) {
    freopen("balancing.in", "r", stdin);
    freopen("balancing.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:141:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |     freopen("input.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:142:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |     freopen("input.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:146:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     freopen("balancing.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:147:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     freopen("balancing.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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