제출 #1307328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307328		erfankaviani	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	835 ms	343424 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define X       first
#define Y       second
#define endl    '\n'

const int MAXN = 2e5 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 2e18;
const int LOG = 22;
const int SQ = 200;

int n , m , q , flag[MAXN] , dp2[MAXN];
vector<int> adj[MAXN] , radj[MAXN];
vector<pii> dp[MAXN];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        int v , u;
        cin >> v >> u;
        adj[v].push_back(u);
        radj[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        vector<pii> vec;
        vec.push_back({-1 , i});
        for(int u : radj[i]){
            merge(vec.begin() , vec.end() , dp[u].begin() , dp[u].end() , back_inserter(dp[i]));
            vec.clear();
            int cnt = 0;
            for(int j = dp[i].size() - 1; j >= 0; j--){
                if(cnt > SQ){
                    break;
                }
                if(flag[dp[i][j].Y] == 0){
                    vec.push_back({dp[i][j].X , dp[i][j].Y});
                    flag[dp[i][j].Y] = 1;
                    cnt++;
                }
            }
            dp[i].clear();
            for(auto j : vec){
                flag[j.Y] = 0;
            }
            reverse(vec.begin() , vec.end());
        }
        dp[i] = vec;
        for(int j = 0; j < dp[i].size(); j++){
            dp[i][j].X++;
        }
    }
    while(q--){
        int v , k;
        cin >> v >> k;
        vector<int> vec;
        for(int i = 0; i < k; i++){
            int u;
            cin >> u;
            flag[u] = 1;
            vec.push_back(u);
        }
        if(k >= SQ){
            dp2[v] = 0;
            for(int i = v - 1; i >= 1; i--){
                dp2[i] = -MOD;
                for(int j : adj[i]){
                    if(j <= v){
                        dp2[i] = max(dp2[i] , dp2[j] + 1);
                    }
                }
            }
            int mx = -1;
            for(int i = 1; i <= v; i++){
                if(flag[i] == 0){
                    mx = max(mx , dp2[i]);
                }
            }
            cout << mx << endl;
            for(int i : vec){
                flag[i] = 0;
            }
            continue;
        }
        int ans = -1;
        for(int j = dp[v].size() - 1; j >= 0; j--){
            if(flag[dp[v][j].Y] == 0){
                ans = dp[v][j].X;
                break;
            }
        }
        for(int i : vec){
            flag[i] = 0;
        }
        cout << ans << endl;
    }

    return 0;
}

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