Submission #605259

#	Time	Username	Problem	Language	Result	Execution time	Memory
605259		alireza_kaviani	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1256 ms	201780 KiB

bitaro

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

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

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;
const ll SQ = 100;

int n , m , q , dp2[MAXN] , mark[MAXN];
vector<int> adj[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[u].push_back(v);
    }

    for(int i = 1 ; i <= n ; i++){
        for(int j : adj[i]){
            vector<pii> vec;
            merge(all(dp[i]) , all(dp[j]) , back_inserter(vec) , greater<pii>());
            dp[i].clear();
            for(pii k : vec){
                if(mark[k.Y])   continue;
                dp[i].push_back(k);
                mark[k.Y] = 1;
            }
            for(pii k : vec){
                mark[k.Y] = 0;
            }
            if(SZ(dp[i]) > SQ){
                dp[i].resize(SQ);
            }
        }
        for(int j = 0 ; j < SZ(dp[i]) ; j++){
            dp[i][j].X++;
        }
        if(SZ(dp[i]) < SQ){
            dp[i].push_back({0 , i});
        }
    }

    while(q--){
        int v , t;
        cin >> v >> t;
        vector<int> vec;
        for(int i = 0 ; i < t ; i++){
            int x; cin >> x;
            vec.push_back(x);
            mark[x] = 1;
        }
        int ans = -1;
        if(t < SQ){
            for(pii i : dp[v]){
                if(!mark[i.Y]){
                    ans = max(ans , i.X);
                }
            }
        }
        if(t >= SQ){
            fill(dp2 , dp2 + MAXN , 0);
            for(int i = 1 ; i <= n ; i++){
                if(mark[i]) dp2[i] = -MOD;
                for(int j : adj[i]){
                    dp2[i] = max(dp2[i] , dp2[j] + 1);
                }
            }
            ans = max(ans , dp2[v]);
        }
        cout << ans << endl;
        for(int i : vec){
            mark[i] = 0;
        }
    }

    return 0;
}
/*

*/

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