Submission #1193675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193675		sopaipilla	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2099 ms	127436 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fst first
#define snd second
using namespace std;

vector<vector<int>> adj;
vector<vector<pair<int,int>>> yth;

vector<pair<int,int>> aux;
vector<int> vst;
void merge(int i, int j) {
    aux.clear();
    int l=0, maxl = yth[i].size()-1;
    int r=0, maxr = yth[j].size()-1;
    vst.clear(), vst.resize(i+1,0);

    int f, s;
    while(aux.size()<=301) {
        if(l<=maxl and r<=maxr) {
            if(yth[i][l].fst > yth[j][r].fst) {
                f=yth[i][l].fst, s=yth[i][l].snd;
                if(!vst[s]) {
                    vst[s]=1;
                    aux.pb({f,s});
                }
                l++;
            } else {
                f=yth[j][r].fst, s=yth[j][r].snd;
                if(!vst[s]) {
                    vst[s]=1;
                    aux.pb({f+1,s});
                }
                r++;
            }
        } else if(l<=maxl) {
            f=yth[i][l].fst, s=yth[i][l].snd;
            if(!vst[s]) {
                vst[s]=1;
                aux.pb({f,s});
            }
            l++;
        } else if(r<=maxr) {
            f=yth[j][r].fst, s=yth[j][r].snd;
            if(!vst[s]) {
                vst[s]=1;
                aux.pb({f+1,s});
            }
            r++;
        } else break;
    }
    yth[i]=aux;
}
void precalc(int n) {
    for(int x=1; x<=n; ++x) {
        yth[x].pb({0,x});
        for(int y : adj[x]) merge(x,y);
    }
}

vector<int> busy;
int solve(int t) {
    for(int i=0; i<=(yth[t].size()-1); ++i) {
        if(!busy[yth[t][i].snd]) return yth[t][i].fst;
    }
    return -1;
}
queue<int> prox;
vector<int> d;
int brute(int t) {
    prox.push(t);
    d.clear(), d.resize(t+1,0);

    int ans=-1, at;
    while(!prox.empty()) {
        at=prox.front(), prox.pop();
        if(!busy[at]) ans=at;
        for(int to : adj[at]) {
            d[to]=d[at]+1;
            prox.push(to);
        }
    }
    
    if(ans==-1) return -1;
    return d[ans];
}

int32_t main() {
    int n, m, q; cin >> n >> m >> q;
    adj.resize(n+1); yth.resize(n+1);
    int a, b;
    while(m-- and cin >> a >> b) adj[b].pb(a);
    precalc(n);

    int t, y;
    while(cin >> t >> y) {
        busy.clear(), busy.resize(n+1,0);
        for(int i=0; i<y; ++i) {
            cin >> a;
            busy[a]=1;
        }

        if(y<=300) cout << solve(t) << endl;
        else cout << brute(t) << endl;
    }
}

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