Submission #1272384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272384		veljko	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2096 ms	14548 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 dfs(int u, vector<vector<int>>& g, vector<bool>& blocked, vector<int>& dp) {
    if (dp[u] != -2) return dp[u]; // already computed

    int best = 0; // path of length 0 (just this node)
    for (int v : g[u]) {
        int res = dfs(v, g, blocked, dp);
        if (res != -1) best = max(best, res + 1);
    }
    if (best == 0 && blocked[u]) return dp[u] = -1;
    return dp[u] = best;
}

int alg1(vector<vector<int>>& g, vector<bool>& blocked, int target) {
    vector<int> dp(g.size(), -2); // -2 = unvisited
    return dfs(target, g, blocked, dp);
}


int alg2(vector<vector<int>>&g, vector<bool>&c, int target){
    vector<int>res(target + 1, -1);
    for (int i=0;i<=target;i++){
        res[i] = (c[i] ? -1 : 0);
        for (auto t : g[i]){
            if (res[t] == -1) continue;
            res[i] = max(res[i], res[t] + 1);
        }
        if (res[i] == 0 && c[i]) res[i] = -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);
    vector<bool>vis(n, false);
    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]--;
            vis[c[i]] = true;
        }
        int ans;
        if (y > sq) ans = alg2(g, vis, target);
        else ans = alg1(g, vis, target);
        cout << ans<<'\n';
        for (int i=0;i<y;i++){
            vis[c[i]] = false;
        } 
    }
}



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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86