제출 #1194735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194735		sopaipilla	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	553 ms	10044 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, Adj;
vector<int> busy, curr;
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) {
    yth.resize(n+1);
    for(int i=1; i<=n; ++i) {
        yth[i].pb({0,i});
        for(int j : Adj[i]) merge(i,j);
    }
}

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

    for(int i=1; i<=t; ++i) {
        if(d[i]==-1) continue;
        for(int j : adj[i]) d[j]=max(d[j],d[i]+1);
    }
    return d[t];
}

int32_t main() {
    int n, m, q;
    cin >> n >> m >> q;
    adj.resize(n+1);
    Adj.resize(n+1);
    for(int i=0; i<m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        Adj[v].pb(u);
    }
    precalc(n);

    busy.resize(n+1,0);
    int t, y;
    while(cin >> t >> y) {
        curr.clear();
        for(int i=0; i<y; ++i) {
            int x;
            cin >> x;
            curr.pb(x);
            busy[x]=1;
        }
        
        if(y<=300) cout << solve(t) << endl;
        else cout << brute(t) << endl;

        for(int x : curr) busy[x]=0;
    }
}

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