Submission #334205

#	Time	Username	Problem	Language	Result	Execution time	Memory
334205		trthminh	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1818 ms	117688 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn=1e5+7,CUT=100;

vector<int> adj[maxn],bck[maxn];

int n, m, q, sz, st, BUSYI[maxn], busy[maxn], dp[maxn];

int slow(int s)
{
    rep (i, 1, n)
        dp[i] = -1e9;
    dp[s] = 0;
    for (int i = s - 1; i >= 1; --i)
    {
        for (auto k : adj[i])
            dp[i] = max (dp[i], dp[k] + 1);
    }
    int mx = -1;
    rep (i, 1, s)
        if (!busy[i])
            mx = max (mx, dp[i]);
    return mx;
}

vector< pair<int,int> > best[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        bck[v].push_back(u);
    }

    vector< pair<int,int> > help={};

    rep (i,1 ,n)
    {
        help={};

        for(auto node_back:bck[i])
            for(auto k:best[node_back])
            help.push_back({k.first+1,k.second});

        help.push_back({0,i});

        sort(help.begin(),help.end());

        reverse(help.begin(),help.end());

        for(auto k:help)
        {
            if(busy[k.second]==0)
            {
                busy[k.second]=1;
                best[i].push_back(k);

                if(best[i].size()==CUT)break;
            }
        }

        for(auto k:best[i])
            busy[k.second]=0;
    }
    for(int i=1;i<=q;i++)
    {
        cin >> st >> sz;
        for(int j=1;j<=sz;j++)
        {
            cin >> BUSYI[j];
            busy[BUSYI[j]]=1;
        }

        if(sz>=CUT)cout << slow(st) << '\n';
        else
        {
            int mx=-1;
            for(auto k:best[st])
                if(busy[k.second]==0)mx=max(mx,k.first);
            cout << mx << '\n';
        }
        for(int j=1;j<=sz;j++)
            busy[BUSYI[j]]=0;
    }
    return 0;
}

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