Submission #1298776

#TimeUsernameProblemLanguageResultExecution timeMemory
1298776Zbyszek99Bitaro’s Party (JOI18_bitaro)C++20
14 / 100
637 ms418012 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int sqr = 320;
vi graph[100001];
vi graph2[100001];
int deg[100001];
bool is_out[100001];
int dp[100001];
vector<pii> best[100001];
vi ls;
int n,m,q2;

void big_query(vi x, int T)
{
    forall(it,ls)
    {
        if(!is_out[it]) dp[it] = 0;
        else dp[it] = -1e9;
        forall(it2,graph[it]) dp[it] = max(dp[it],dp[it2]+1);
        if(it == T)
        {
            cout << max(-1,dp[it]) << "\n";
        }
    }
}

vector<pii> merge_dp(vector<pii>& v1, vector<pii>& v2)
{
    int p1 = 0;
    int p2 = 0;
    vector<pii> ans;
    forall(it,v2) it.ff++;
    rep(i,min(siz(v1)+siz(v2),sqr))
    {
        if(p1 == siz(v1)) ans.pb(v2[p2++]);
        else if(p2 == siz(v2)) ans.pb(v1[p1++]);
        else
        {
            if(v1[p1].ff >= v2[p2].ff) ans.pb(v1[p1++]);
            else ans.pb(v2[p2++]);
        }
    }
    forall(it,v2) it.ff--;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> n >> m >> q2;
    rep(i,m)
    {
        int a,b;
        cin >> a >> b;
        graph[b].pb(a);
        graph2[a].pb(b);
    }
    rep2(i,1,n) deg[i] = siz(graph[i]);
    queue<int> q;
    rep2(i,1,n) if(deg[i] == 0) q.push(i);
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        ls.pb(t);
        forall(it,graph2[t])
        {
            deg[it]--;
            if(deg[it] == 0) q.push(it);
        }
    }
    forall(it,ls)
    {
        best[it] = {{0,it}};
        forall(it2,graph[it])
        {
            best[it] = merge_dp(best[it],best[it2]);
        }
    }
    rep(qq,q2)
    {
        int t,y;
        cin >> t >> y;
        vi x(y);
        rep(j,y) cin >> x[j];
        forall(it,x) is_out[it] = 1;
        if(y >= sqr) big_query(x,t);
        else
        {
            int ans = -1;
            forall(it,best[t]) if(!is_out[it.ss]) ans = max(ans,it.ff);
            cout << ans << "\n";
        }
        forall(it,x) is_out[it] = 0;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...