Submission #1285331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285331		alizhan	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1133 ms	283464 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod =  1e9 + 7;
const int N = (int)1e6 + 7;
#define skip continue
#define uno first
#define duo second
#define GO while(tt--)
#define ins insert
#define pb push_back
#define all(x) x.begin(), x.end()
#define Kaldun ios::sync_with_stdio(false); cin.tie(nullptr)
#define int long long

int bp(int a, int n) {
    if(n == 0) return 1;
    if(n % 2 == 1) return (bp(a, n-1) * a) % mod;
    long long b = bp(a, n/2);
    return (b * b) % mod;
}
int r,n,m,q;
vector<int>g[N];
int dp[N][3],dis[N],del[N];
vector<pair<int,int>>l[N];
void dfs(){
    for(int u=1;u<=n;u++){
        vector<int>v;
        v.push_back(u);
        l[u].push_back({0,u});
        dp[u][0] = 0;
        dp[u][1] = u+1;
        for(auto to : g[u]){
            for(auto x : l[to]){
                if(dp[x.second][1] != u + 1){
                    v.push_back(x.second);
                    dp[x.second][1] = u + 1;
                    dp[x.second][0] = x.first + 1;
                }
                else dp[x.second][0] = max(dp[x.second][0] , x.first + 1);
            }
        }
        for(int to : v){
            l[u].push_back({dp[to][0], to});
        }
        
        sort(l[u].begin(), l[u].end(), greater<pair<int, int>>());
        
        int len = l[u].size();
        while(len > 100){
            l[u].pop_back();
            len--;
        }
    }
}
void bfs(int x){
    fill(dis + 1,dis + n + 1 , 0);
    for(int u=1;u<=r;u++){
        for(int to : g[u]){
            dis[u] = max(dis[u] ,dis[to] + 1);
        }
        if(dis[u] == 0 && del[u] == x){
            dis[u] = -1;
        }
    }
}
int lcm(int a,int b){ return (a * b) / __gcd(a,b);}
void solve() {
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int ll,rr;
        cin>>ll>>rr;
        g[rr].push_back(ll);
    }
    if(q>1) dfs();
    for(int i=1;i<=q;i++){
        int x;
        cin>>r>>x;
        for(int j=0;j<x;j++){
            int pop;
            cin>>pop;
            del[pop] = i;
        }
        if(x >= 100 || q==1){
            bfs(i);
            cout<<dis[r]<<endl;
        }
        else{
            int res = -1;
            for(int j = 0; j < l[r].size(); j++){
                if(del[l[r][j].second] != i){
                    res = l[r][j].first;
                    break;
                }
            }
            cout<<res<<endl;
        }
    }
}
signed main() {
    Kaldun;
    cout.precision(0);
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    int tt=1;
    //cin>>tt;
    while(tt--){
        solve();
    }
}

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