Submission #416803

#	Time	Username	Problem	Language	Result	Execution time	Memory
416803		paulomiranda98	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1894 ms	99028 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 = 100;

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

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

int solve(int u, vector<int> &v){
  int ans = -1;
  if(v.size() < SQRT){
    T++;
    for(int to: v){
      used2[to] = T;
    }
    for(auto [d, to]: dist[u]){
      if(used2[to] < T){
        ans = d;
        break;
      }
    }
  }else{
    memset(dp, -1, sizeof(dp));
    memset(invalid, 0, sizeof(invalid));
    for(int to: v)
      invalid[to] = true;
    ans = max(-1, dfs(u));
  }
  return ans;

}
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=1; i<=n; i++)
    precompute(i);
  
  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];
    cout << solve(t, v) << endl;
  }
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int solve(int, std::vector<int>&)':
bitaro.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [d, to]: dist[u]){
      |              ^

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