Submission #751474

#	Time	Username	Problem	Language	Result	Execution time	Memory
751474		Valters07	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2071 ms	13244 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+5;
const int B = 100;
vector<int> g[N];
set<pair<int,int> > best[N];
int main()
{
    fio
//    ifstream cin("in.in");
    int n, m, q;
    cin >> n >> m >> q;
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
    }
    for(int i = 1;i<=n;i++)
        best[i].insert({0,i});
    for(int i = 1;i<=n;i++)
    {
        for(auto j:g[i])
        {
            for(auto t = best[i].rbegin();t!=best[i].rend()&&(*t).fi+1>(*best[j].begin()).fi;t++)
            {
                best[j].insert({(*t).fi+1,(*t).se});
                if(best[j].size()>B)
                    best[j].erase(best[j].begin());
            }
        }
    }
    for(int qi = 1;qi<=q;qi++)
    {
        int f, y;
        cin >> f >> y;
        vector<int> del(y);
        for(auto &x:del)
            cin >> x;
        if(y<B)
        {
            set<int> s;
            for(auto x:del)
                s.insert(x);
            auto t = --best[f].end();
            while(t!=best[f].begin()&&s.count((*t).se))
                t--;
            if(s.count((*t).se))
                cout << -1;
            else
                cout << (*t).fi;
        }
        else
        {
            vector<int> dist(n+1);
            for(auto x:del)
                dist[x]=-1e9;
            for(int i = 1;i<=f;i++)
                for(auto j:g[i])
                    dist[j]=max(dist[j],dist[i]+1);
            if(dist[f]<0)
                cout << -1;
            else
                cout << dist[f];
        }
        cout << "\n";
    }
//    cin.close();
    return 0;
}

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