Submission #597727

#	Time	Username	Problem	Language	Result	Execution time	Memory
597727		ctd6969	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1694 ms	419904 KiB

bitaro

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

typedef long long ll;

using pl = pair<ll,ll>;
using pi = pair<int,int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;

#define mp make_pair
#define f first
#define s second

#define foru(i,a,b) for(int i = a ; i <= b;i++)
#define ford(i,a,b) for(int i = a ; i >= b;i--)

#define psh push
#define em emplace
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(),(x).end()


int n , m , q , u , v , t,y;
vi E[100005];
vi backward[100005];
vpi save[100005];
const int BLOCK_SIZE = 500;
bool notok[100005];
int forbid[100005] , dp[100005];
bool vis[100005];
int main(){

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("D:/.vscode/Codeforces/input.txt","r",stdin);
	// freopen("D:/.vscode/Codeforces/output.txt","w",stdout);

    cin >> n >> m >> q;
    foru(i,1,m){
        cin >> u >> v;
        E[u].eb(v);
        backward[v].eb(u);
    }
    foru(i,1,n){
        for(int d : backward[i]){
            vpi temp;
            save[d].pb({0,d});
            int p1 = 0 , p2 = 0 , a = save[d].size() , b=  save[i].size();
            while(temp.size() < BLOCK_SIZE && (p1 < a || p2 < b)){
                if(p2==b || (p1!=a&& save[d][p1].f + 1 >= save[i][p2].f)){
                    temp.pb({save[d][p1].f+1,save[d][p1].s});
                    vis[save[d][p1].s] = 1;
                    p1++;
                }
                else {
                    temp.pb(save[i][p2]);
                    vis[save[i][p2].s] = 1;
                    p2++;
                }
                while(p1<a&&vis[save[d][p1].s]) p1++;
                while(p2<b&&vis[save[i][p2].s]) p2++;
            }
            save[d].pop_back();
            for(auto x : temp) vis[x.s] = 0;
            swap(temp,save[i]);
        }
    }
    foru(i,1,q){
        cin >> t >> y;
        int ans = -1;
        foru(j,1,y){
            cin >> forbid[j];
            notok[forbid[j]] = 1;
        }
        if(!notok[t]) ans = 0;
        if(y < BLOCK_SIZE){
            foru(j,0,(int)save[t].size() - 1){
                if(!notok[save[t][j].s]){
                    ans = max(ans,save[t][j].f);
                    break;
                }
            }
        }
        else {
            foru(j,1,n) dp[j] = -1;
            dp[t] = 0; 
            ford(j,t-1,1){
                for(int x : E[j]){
                    if(dp[x] != -1) dp[j] = max(dp[j], dp[x] + 1);
                }
                if(!notok[j]) ans = max(ans,dp[j]);
            }
        }
        cout << ans << '\n';
        foru(j,1,y) notok[forbid[j]] = 0;
    }
}

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