Submission #201614

#	Time	Username	Problem	Language	Result	Execution time	Memory
201614		Sensei	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2088 ms	10720 KiB

bitaro

/*
	DATE:		2020-02-11 14:19:26
	NAME:		
	PROBLEM:	JOI18_BITARO
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

const int SQRT = 150;

vector<int> edge[MAXN + 7];
vector<int> redge[MAXN + 7];
int dp[MAXN + 7];

bool vis[MAXN + 7];
vector<pair<int, int> > sqrt_furthest[MAXN + 7];

void sqrt_dfs(int u) {
  vis[u] = true;
  for (int i = 0; i < (int) redge[u].size(); i++) {
    int v = redge[u][i];
    if (!vis[v]) {
      sqrt_dfs(v);
    }
  }
  vector<pair<int, int> > ans;
  ans.push_back({0, u});
  for (int i = 0; i < (int) redge[u].size(); i++) {
    int v = redge[u][i];
    vector<pair<int, int> > copy_ans;
    swap(ans, copy_ans);
    // copy_ans.push_back({1, v});
    unordered_set<int> in;
    int x = 0;
    int y = 0;
    while (ans.size() < SQRT and x < (int) sqrt_furthest[v].size() and y < (int) copy_ans.size()) {
      if (in.find(sqrt_furthest[v][x].second) != in.end()) {
        x++;
        continue;
      }
      if (in.find(copy_ans[y].second) != in.end()) {
        y++;
        continue;
      }
      if (sqrt_furthest[v][x].first + 1 > copy_ans[y].first) {
        ans.push_back({sqrt_furthest[v][x].first + 1, sqrt_furthest[v][x].second});
        in.insert(sqrt_furthest[v][x].second);
      }
      else {
        ans.push_back(copy_ans[y]);
        in.insert(copy_ans[y].second);
      }
    }
    while (ans.size() < SQRT and x < (int) sqrt_furthest[v].size()) {
      if (in.find(sqrt_furthest[v][x].second) != in.end()) {
        x++;
        continue;
      }
      ans.push_back({sqrt_furthest[v][x].first + 1, sqrt_furthest[v][x].second});
      in.insert(sqrt_furthest[v][x].second);
    }
    while (ans.size() < SQRT and y < (int) copy_ans.size()) {
      if (in.find(copy_ans[y].second) != in.end()) {
        y++;
        continue;
      }
      ans.push_back(copy_ans[y]);
      in.insert(copy_ans[y].second);
    }
  }
  sqrt_furthest[u] = ans;
}

void naive_dfs(int u, vector<bool> &disallowed) {
  vis[u] = true;
  if (disallowed[u] == true) {
    dp[u] = -1;
  }
  else {
    dp[u] = 0;
  }
  for (int i = 0; i < (int) redge[u].size(); i++) {
    int v = redge[u][i];
    if (!vis[v]) {
      naive_dfs(v, disallowed);
    }
    if (dp[v] != -1) {
      dp[u] = max(dp[u], 1 + dp[v]);
    }
  }
}

int main() {
  int n, m, q;
  cin >> n >> m >> q;

  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    edge[u].push_back(v);
    redge[v].push_back(u);
  }

  for (int u = 1; u <= n; u++) {
    if (!vis[u]) {
      sqrt_dfs(u);
    }
  }

  for (int i = 1; i <= q; i++) {
    int u;
    scanf("%d", &u);
    int cnt;
    scanf("%d", &cnt);
    vector<int> disallowed(cnt);
    for (int j = 0; j < cnt; j++) {
      scanf("%d", &disallowed[j]);
    }
    if (cnt >= SQRT) {
      memset(vis, 0, sizeof vis);
      vector<bool> copy_disallowed(n + 1, false);
      for (int j = 0; j < (int) disallowed.size(); j++) {
        copy_disallowed[disallowed[j]] = true;
      }
      naive_dfs(u, copy_disallowed);
      printf("%d\n", dp[u]);
    }
    else {
      int ans = -1;
      unordered_set<int> copy_disallowed;
      for (int j = 0; j < (int) disallowed.size(); j++) {
        copy_disallowed.insert(disallowed[j]);
      }
      for (int j = 0; j < (int) sqrt_furthest[u].size(); j++) {
        if (copy_disallowed.find(sqrt_furthest[u][j].second) == copy_disallowed.end()) {
          ans = sqrt_furthest[u][j].first;
          break;
        }
      }
      printf("%d\n", ans);
    }
  }

  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &u, &v);
     ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &u);
     ~~~~~^~~~~~~~~~
bitaro.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &cnt);
     ~~~~~^~~~~~~~~~~~
bitaro.cpp:120:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &disallowed[j]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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