Submission #815472

#	Time	Username	Problem	Language	Result	Execution time	Memory
815472		Sogol	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1751 ms	435768 KiB

bitaro

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

typedef long long ll;
 
#define pb       push_back
#define Sz(x)    int((x).size())
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear

const int maxn  =  1e5   + 10;
const int maxa  =  2e9   +  5;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;
const double eps = 1e-9;

vector <int> vc, adj[maxn], ajd[maxn];
vector <pair <int, int> > mx[maxn];
bool f[maxn], mark[maxn];
int dp[maxn], sq;

inline void dfs(int v){
    mark[v] = 1;
    mx[v].pb({0, v});
    for (int u : ajd[v]){
        if(!mark[u]) dfs(u);
        vector <pair <int, int> > vc = mx[v], uc = mx[u];
        for (int i = 0; i < Sz(uc); i ++) uc[i].fi ++;
        mx[v].cl();
        int p1 = 0, p2 = 0;
        while (p1 < Sz(vc) || p2 < Sz(uc)){
            if(p2 == Sz(uc) || (p1 < Sz(vc) && vc[p1].fi > uc[p2].fi)){
                if(!f[vc[p1].se]) mx[v].pb(vc[p1]), f[vc[p1].se] = 1;
                p1 ++;
            }
            else{
                if(!f[uc[p2].se]) mx[v].pb(uc[p2]), f[uc[p2].se] = 1;
                p2 ++;
            }
        }
        for (auto p : mx[v]) f[p.se] = 0;
        while (Sz(mx[v]) > sq) mx[v].pop_back();
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    sq = sqrt(n);
    for (int i = 0; i < m; i ++){
        int v, u;
        cin >> v >> u;
        adj[v].pb(u);
        ajd[u].pb(v);
    }
    for (int i = n; i >= 1; i --){
        if(!mark[i]) dfs(i);
    }
    while(q --){
        int t, y;
        cin >> t >> y;
        vc.cl();
        for (int i = 0; i < y; i ++){
            int c;
            cin >> c;
            vc.pb(c);
            for (int c : vc) f[c] = 1;
        }
        int ans = -1;
        if(y >= sq){
            fill(dp, dp + n + 10, -mod);
            dp[t] = 0;
            for (int i = t; i >= 1; i --){
                for (int j : adj[i]) dp[i] = max(dp[i], dp[j] + 1);
                if(!f[i]) ans = max(ans, dp[i]);
            }
        }
        else{
            for (auto p : mx[t]) if(!f[p.se]) ans = max(ans, p.fi);
        }
        for (int c : vc) f[c] = 0;
        cout << ans << '\n';
    }
    return 0;
}

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