Submission #416800

#	Time	Username	Problem	Language	Result	Execution time	Memory
416800		paulomiranda98	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2093 ms	14140 KiB

bitaro

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define endl '\n'

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};

const int MAXN = 100010;
const int SQRT = 700;

vector<pair<int, vector<int>>> queries[MAXN];
vector<int> adj[MAXN];
vector<pii> dist[MAXN];

int ans[MAXN], used1[MAXN], used2[MAXN];

void precompute(int u){
  vector<pii> aux;
  aux.emplace_back(0, u);
  dist[u].assign(SQRT, pii(0, u));
  for(int to: adj[u]){
    for(pii p: dist[to]){
      p.F++;
      aux.push_back(p);
    }
  }
  sort(all(aux), greater<pii>());
  int i = 0;
  for(auto p: aux){
    if(used1[p.S] < u){
      dist[u][i++] = p;
      used1[p.S] = u;
      
      if(i == SQRT)
        break;
    }
  }
}

int dp[MAXN];
bool invalid[MAXN];

int dfs(int u){
  if(dp[u] != -1)
    return dp[u];
  int res = invalid[u] ? -INF : 0;
  for(int to: adj[u])
    res = max(res, dfs(to) + 1);
  return dp[u] = res;
}
int T;

void solve(int u){
  precompute(u);
  for(auto [id, v]: queries[u]){
    ans[id] = -1;
    if(v.size() < SQRT){
      T++;
      for(int to: v)
        used2[to] = T;
      for(auto [d, to]: dist[u]){
        if(used2[to] < T){
          ans[id] = d;
          break;
        }
      }
    }else{
      memset(dp, -1, sizeof(dp));
      memset(invalid, 0, sizeof(invalid));
      for(int to: v)
        invalid[to] = true;
      ans[id] = dfs(u);
    }
    ans[id] = max(ans[id], -1);
  }
}
int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);

  int n, m, q;
  cin >> n >> m >> q;
  for(int i=0; i<m; i++){
    int a, b;
    cin >> a >> b;
    adj[b].push_back(a);
  }
  for(int i=0; i<q; i++){
    int t, y;
    cin >> t >> y;
    vector<int> v(y);
    for(int j=0; j<y; j++)
      cin >> v[j];
    queries[t].emplace_back(i, v);
  }
  for(int i=1; i<=n; i++){
    solve(i);
  }
  for(int i=0; i<q; i++){
    cout << ans[i] << endl;
  }
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve(int)':
bitaro.cpp:64:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |   for(auto [id, v]: queries[u]){
      |            ^
bitaro.cpp:70:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |       for(auto [d, to]: dist[u]){
      |                ^

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