Submission #966263

#	Time	Username	Problem	Language	Result	Execution time	Memory
966263		A7med_Mousa	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1417 ms	415300 KiB

bitaro

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <cassert>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
vector<int>val;
bool comp(int &a, int &b){
    return val[a] > val[b];
}


void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<int>adj[n];
    for (int i = 0 ; i < m; ++i){
        int u, v; cin >> u >> v;
        --u, --v;
        adj[v].emplace_back(u);
    }
    vector<int>vis(n);
    val.resize(n);

    int sq = sqrt(n);
    vector<vector<pair<int ,int>>>dp(n);
    for (int node = 0; node < n; ++node){
        vector<int>cur;
        cur.emplace_back(node);
        val[node] = 0;
        vis[node] = node;
        for (int &child : adj[node]){
            for (auto &[value , cur_node] : dp[child]){
                if (vis[cur_node] != node){
                    vis[cur_node] = node;
                    val[cur_node] = value + 1;
                    cur.emplace_back(cur_node);
                }
                else
                    val[cur_node] = max(val[cur_node], value + 1);
            }
        }
        sort(cur.begin(), cur.end(),comp);
        int sz = (int) cur.size();
        for (int i = 0; i < min(sz, sq); ++i)
            dp[node].emplace_back(make_pair(val[cur[i]], cur[i]));
    }
    vector<int>take(n);
    for (int i = 1; i <= q; ++i){
        int node; cin >> node;
        --node;
        int total; cin >> total;
        int y = total;
        while(total--){
            int x; cin >> x;
            --x;
            take[x] = i;
        }
        total = y;
        if (total >= sq){
            vector<int>dp1(n, -1);
            dp1[node] = 0;
            int ans = (take[node] == i ? -1 : 0);
            for (int j = node; j >= 0; --j){
                if (take[j] != i)
                    ans = max(ans, dp1[j]);
                for (int &child : adj[j])
                    dp1[child] = max(dp1[child], dp1[j] + (dp1[j] != -1));
            }
            cout << ans << '\n';
        }
        else {
            bool x = 1;
            for (auto &[val, cur_node] : dp[node])
                if (take[cur_node] != i){
                    cout << val << '\n';
                    x = 0;
                    break;
                }
                if (x)
                    cout << -1 << '\n';
        }
    }
}

int main()
{
    fast;
    int t = 1; //cin >> t;
    for (int i = 1 ; i <= t; ++i){
        solve();
        if (i != t)
            cout << '\n';
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:34:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |             for (auto &[value , cur_node] : dp[child]){
      |                        ^
bitaro.cpp:75:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |             for (auto &[val, cur_node] : dp[node])
      |                        ^
bitaro.cpp:75:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |             for (auto &[val, cur_node] : dp[node])
      |             ^~~
bitaro.cpp:81:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |                 if (x)
      |                 ^~

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