Submission #1272335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272335		veljko	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2108 ms	344496 KiB

bitaro

/*****from dust I have come, dust I will be*****/
#include <algorithm>
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
const int MOD = 1000000007;
using namespace std;
#define int long long
#define forn(i,n) for(int i=0;i<n;i++)
int dx[8] = { 1, 0, -1, 0, -1, 1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, -1, 1, 1, -1 };
int ceil_div(int a, int b) {return a % b == 0 ? a / b : a / b + 1;}
int add(int x, int y)  { return (x%MOD + y%MOD)%MOD; }
int sub(int x, int y)  { return (x%MOD - y%MOD + MOD)%MOD; }
int mul(int x, int y)  { return (x%MOD * y%MOD)%MOD; }

//const int MOD = 998244353;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

/*
int k = A.order_of_key(p[i].second);
A.erase(A.find_by_order(k));
erase element from pbds multiset
*/

int alg1(vector<vector<int>>&g, vector<int>&c, int target){
    vector<int>res(target+1, -1);
    for (int i=0;i<=target;i++){
        if (binary_search(c.begin(), c.end(), i)) continue;
        queue<pair<int, int>>q;
        q.push({i, 0});
        while (!q.empty()){
            auto t = q.front();
            res[t.first] = max(res[t.first], t.second);
            q.pop();
            for (auto x : g[t.first]){
                if (x > target) continue;
                q.push({x, t.second + 1});
            }
        }
    }
    return res[target];
}

int alg2(vector<vector<int>>&g, vector<int>&c, int target){
    vector<int>res(target + 1, -1);
    for (int i=0;i<=target;i++){
        res[i] = (binary_search(c.begin(), c.end(), i) ? -1 : 0);
        for (auto t : g[i]){
            if (res[t] == -1) continue;
            res[i] = max(res[i], res[t] + 1);
        }
    }
    return res[target];
}

void solve() {
    int n,m,q; cin >> n >> m >> q;
    vector<vector<int>>g(n), f(n);
    for (int i=0;i<m;i++){
        int a,b; cin >> a>> b;
        a--; b--;
        g[b].push_back(a);
        f[a].push_back(b);
    }

    int sq = sqrtl(n);
    for (int i=0;i<q;i++){
        int target, y; cin >> target>> y;
        target--;
        vector<int>c(y);
        for (int i=0;i<y;i++){
            cin >> c[i];
            c[i]--;
        }
        int ans;
        if (y > sq) ans = alg1(f, c, target);
        else ans = alg2(g, c, target);
        cout << ans<<'\n';
    }
}



int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

    int t = 1;// cin >>t;
    for (int i=1;i<=t;i++){
        solve();
    }
    return 0;
}

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