Submission #1160938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160938		Hamed_Ghaffari	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	513 ms	241516 KiB

bitaro

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

using pii = pair<int, int>;

#define X first
#define Y second
#define pb push_back

const int MXN = 1e5+5;
const int sq  = 300;

int n, m, q, dis[MXN];
vector<int> g[MXN];
pii dp[MXN][sq];
pii tmp[sq];
bool mark[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=0, u,v; i<m; i++) {
        cin >> u >> v;
        g[v].pb(u);
    }
    for(int v=1; v<=n; v++) {
        dp[v][0] = pii(0, v);
        fill(dp[v]+1, dp[v]+sq, pii(-1, -1));
        for(int u : g[v]) {
            int i=0, j=0, k=0;
            while(i<sq && dp[v][i].X!=-1 && j<sq && dp[u][j].X!=-1 && k<sq)
                if(dp[v][i].X>=dp[u][j].X+1){
                    if(!mark[dp[v][i].Y]) tmp[k++] = dp[v][i];
                    mark[dp[v][i].Y]=1;
                    i++;
                }
                else {
                    if(!mark[dp[u][j].Y]) tmp[k++] = pii(dp[u][j].X+1, dp[u][j].Y);
                    mark[dp[u][j].Y]=1;
                    j++;
                }
            while(i<sq && dp[v][i].X!=-1 && k<sq) {
                if(!mark[dp[v][i].Y]) tmp[k++] = dp[v][i];
                mark[dp[v][i].Y]=1;
                i++;
            }
            while(j<sq && dp[u][j].X!=-1 && k<sq) {
                if(!mark[dp[u][j].Y]) tmp[k++] = pii(dp[u][j].X+1, dp[u][j].Y);
                mark[dp[u][j].Y]=1;
                j++;
            }
            for(int x=0; x<k; x++)
                mark[(dp[v][x]=tmp[x]).Y] = 0;
        }
    }
    while(q--) {
        int t, y;
        cin >> t >> y;
        vector<int> c(y);
        for(int &i : c) cin >> i;
        for(int i : c) mark[i] = 1;
        if(y<sq) {
            int ans=-1;
            for(int i=0; i<sq; i++)
                if(dp[t][i].X!=-1 && !mark[dp[t][i].Y]) {
                    ans = dp[t][i].X;
                    break;
                }
            cout << ans << '\n';
        }
        else {
            fill(dis+1, dis+n+1, -1e9);
            dis[t] = 0;
            int ans=-1;
            for(int v=t; v>=1; v--) {
                for(int u : g[v])
                    dis[u] = max(dis[u], dis[v]+1);
                if(!mark[v]) ans = max(ans, dis[v]);
            }
            cout << ans << '\n';
        }
        for(int i : c) mark[i] = 0;
    }
    return 0;
}

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