제출 #1109553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1109553		tinnhiemnn	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	4 ms	5436 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define file "test"
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
const int N=1e5+2;
int n,m,q,dp[N];
vector<int> E[N];
vector<pii> f[N];

int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m>>q;
    for (int i=1;i<=m;i++)
    {
        int u,v; cin>>u>>v; E[v].pb(u);
    }

    for (int i=1;i<=n;i++)
    {
        f[i].pb({0, i});
        vector<int> tmp, dis(n+1, -1);

        for (int j : E[i]) for (pii p : f[j])
        {
            int u=p.second, w=p.first;
            if (dis[u] == -1)
            {
                tmp.pb(u); dis[u]=w+1;
            }
            else dis[u]=max(dis[u], w+1);
        }

        for (int u : tmp) f[i].pb({dis[u], u});
        sort(f[i].rbegin(), f[i].rend());

        while (f[i].size() > 100) f[i].pop_back();
    }


    while (q--)
    {
        int t,k; cin>>t>>k;
        vector<bool> ok(n+1, 0); for (int i=1;i<=k;i++) {int x; cin>>x; ok[x]=1;}

        if (k >= 100)
        {
            int res=-1;
            for (int i=t;i>=1;i--) dp[i]=0;
            for (int i=t;i>=1;i--)
            {
                if (ok[i]) continue;
                res=max(res, dp[i]);
                for (int v : E[i]) dp[v]=max(dp[v], dp[i]+1);
            }

            cout<<res<<'\n';
        }
        else {
            int res=-1;
            for (pii p : f[t]) if (!ok[p.second]) {res=p.first; break;}
            cout<<res<<'\n';
        }
    }
}

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