제출 #1272599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272599		veljko	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	3 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 dfs(int u, vector<vector<int>>& g, vector<bool>& blocked, vector<int>& dp) {
    if (dp[u] != -2) return dp[u];

    int best = 0; 
    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;
}

vector<int> alg1(vector<vector<int>>& g, vector<bool>& blocked, int target) {
    vector<int> dp(target+1, -2);
    dfs(target, g, blocked, dp);
    return dp;
}



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);
    vector<int>dp = alg1(g, vis, n - 1);
    for (int i=0;i<q;i++){
        int target, y; cin >> target>> y;
        target--;
        vector<int>c(y);
        queue<int>q;
        for (int i=0;i<y;i++){
            cin >> c[i];
            c[i]--;
            vis[c[i]] = true;
        }
        vector<int>tmp = dp;
        for (int i=0;i<y;i++){
            if (dp[c[i]] == 0){
                dp[c[i]] = -1;
                q.push(c[i]);
                while (!q.empty()){
                    auto t = q.front(); q.pop();
                    for (auto x : f[t]){
                        dp[x] = 0;
                        for (auto y : g[x]){
                            dp[x] = max(dp[x], dp[y] + 1);
                        }
                        if (dp[x] == 0 && vis[x]){
                            dp[x] = -1;
                        }
                        q.push(x);
                    }   
                }
            }
        }
        // for (auto t : dp) cout << t<<' ';
        // cout << '\n';
        cout << dp[target]<<'\n';

        for (int i=0;i<y;i++){
            vis[c[i]] = false;
            if (dp[c[i]] == -1){
                dp[c[i]] = 0;
                q.push(c[i]);
                while (!q.empty()){
                    auto t = q.front(); q.pop();
                    for (auto x : f[t]){
                        dp[x] = 0;
                        for (auto y : g[x]){
                            dp[x] = max(dp[x], dp[y] + 1);
                        }
                        q.push(x);
                    }   
                }
            }
        }

    }
}



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