제출 #416786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416786		paulomiranda98	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2059 ms	14244 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);
  for(int to: adj[u]){
    for(pii p: dist[to]){
      p.F++;
      aux.push_back(p);
    }
  }
  sort(all(aux), greater<pii>());
  for(auto p: aux){
    if(used1[p.S] < u){
      dist[u].push_back(p);
      used1[p.S] = u;
      
      if(dist[u].size() == 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] = max(-1, dfs(u));
    }
  }
}
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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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