제출 #1104409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104409		anmattroi	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	684 ms	146760 KiB

bitaro

#include <bits/stdc++.h>

#define maxn 100005

using namespace std;

const int B = 100;

int n, m, q;
vector<int> adj[maxn];
vector<pair<int, int> > best[maxn];
int from[maxn];
int dd[maxn];
int a[maxn];
int dp[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) from[i] = -1;

    for (int u = 1; u <= n; u++) {
        best[u].emplace_back(0, u);
        vector<int> from_indices;
        for (int v : adj[u]) {
            for (auto [w, x] : best[v]) {
                if (from[x] == -1) {
                    from[x] = w + 1;
                    from_indices.emplace_back(x);
                } else from[x] = max(from[x], w+1);
            }
        }
        for (int i : from_indices) {best[u].emplace_back(from[i], i); from[i] = -1;}
        sort(best[u].begin(), best[u].end(), greater<pair<int, int> >());
        while (best[u].size() > B) best[u].pop_back();
        from_indices.clear();
    }
    auto sub1 = [&](int s, int k) {
        for (int i = 0; i < k; i++) {
            cin >> a[i];
            dd[a[i]] = 1;
        }
        int ds = INT_MIN;
        for (auto [w, x] : best[s]) {
            if (dd[x]) continue;
            ds = max(ds, w);
        }
        cout << (ds == INT_MIN ? -1 : ds) << "\n";
        for (int i = 0; i < k; i++) dd[a[i]] = 0;
    };
    auto sub2 = [&](int s, int k) {
        for (int i = 1; i <= n; i++) dp[i] = 0;
        for (int i = 0; i < k; i++) {
            cin >> a[i];
            dp[a[i]] = INT_MIN/10;
        }
        for (int i = 1; i <= s; i++) {
            for (int j : adj[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        cout << max(dp[s], -1) << "\n";
    };
    while (q--) {
        int s, k;
        cin >> s >> k;
        if (k >= 100) sub2(s, k);
        else sub1(s, k);
    }
}

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:33:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |             for (auto [w, x] : best[v]) {
      |                       ^
bitaro.cpp: In lambda function:
bitaro.cpp:51:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for (auto [w, x] : best[s]) {
      |                   ^

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