Submission #1303336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303336		oloc	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	710 ms	211504 KiB

bitaro

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vect;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pb push_back
#define f first
#define s second

const int N = 1e5 + 1;
const int sq = 200;
vector<int> graf[N];

vector<pii> merguj(vector<pii>& a, vector<pii>& b, vector<int>& odw, int tmp){
    vector<pii> wyn;
    int n = a.size(), m = b.size();
    int i = 0, j = 0;
    while(i < n && j < m && wyn.size() < sq){
        while(i < n && odw[a[i].s] == tmp){
            i++;
        }
        while(j < m && odw[b[j].s] == tmp){
            j++;
        }
        if(i == n || j == m) break;

        if(a[i].f > b[j].f){
            wyn.pb({a[i].f, a[i].s});
            odw[a[i].s] = tmp;
            i++;
        }else{
            wyn.pb({b[j].f + 1, b[j].s});
            odw[b[j].s] = tmp;
            j++;
        }
    }

    while(i < n && wyn.size() < sq){
        while(i < n && odw[a[i].s] == tmp){
            i++;
        }
        if(i == n) break;
        wyn.pb({a[i].f, a[i].s});
        odw[a[i].s] = tmp;
        i++;
    }

    while(j < m && wyn.size() < sq){
        while(j < m && odw[b[j].s] == tmp){
            j++;
        }
        if(j == m) break;
        wyn.pb({b[j].f + 1, b[j].s});
        odw[b[j].s] = tmp;
        j++;
    }

    return wyn;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graf[b].pb(a);
    }

    vector<vector<pii>> best_sq(n + 1);
    vector<int> odw(n + 1, 0);

	int it = 1;
    for(int i = 1; i <= n; i++){
        for(int u : graf[i]){
            best_sq[i] = merguj(best_sq[i], best_sq[u], odw, it++);
        }
        if(best_sq[i].size() < sq){
            best_sq[i].pb({0, i});
        }
    }



    vector<int> zak(n + 1, 0);
    for(int i = 1; i <= q; i++){
        int t, x;
        cin >> t >> x;
        for(int j = 0; j < x; j++){
            int a;
            cin >> a;
            zak[a] = i;
        }
        if(x >= sq / 2){
            vector<int> dp(n + 1, -1e9);
            dp[t] = 0;
            for(int v = t; v >= 1; v--){
                for(int u : graf[v]){
                    dp[u] = max(dp[u], dp[v] + 1);
                }
                if(zak[v] == i){
                    dp[v] = -1;
                }
            }
            int best = -1;
            for(int v = 1; v <= t; v++){
                best = max(best, dp[v]);
            }
            cout << best << "\n";
        }else{
            bool flaga = true;
            for(pii a : best_sq[t]){
                int val = a.f, v = a.s;
                if(zak[v] != i){
                    cout << val << "\n";
                    flaga = false;
                    break;
                }
            }
            if(flaga) cout << "-1\n";
        }
    }

//    cout << "\n";
//    for(int i = 1; i <= n; i++){
//        cout << "i: " << i << "\n";
//        for(pii a : best_sq[i]){
//            cout << "v: " << a.s << " val: " << a.f << "\n";
//        }
//    }

    return 0;
}

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