제출 #1272379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272379		veljko	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2095 ms	656 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<bool>& blocked, int target){
    int mx = (blocked[target] ? -1 : 0);
    for (auto t : g[target]){
        mx = max(mx, alg1(g, blocked, t) + 1);
    }
    if (mx == 0 && blocked[target]) return -1;
    return mx;
}


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);
        }
    }
    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 = 0;
    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 = alg1(g, vis, target);
        else ans = alg2(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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86