제출 #160415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160415		combi1k1	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2067 ms	395104 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  push_back
#define ii  pair<int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 1e5 + 1;
const int   B   = 250;

vector<int> g[N];

vector<ii>  opt[N];

int vis[N];
int ban[N];
int len[N];
int tot = 1;

int dfs(int u)  {
    if (vis[u]) return  0;

    vis[u] = 1;
    opt[u].pb(ii(0,u));

    for(int v : g[u])  {
        dfs(v);
        for(ii  e : opt[v])
            opt[u].pb(ii(e.X + 1,e.Y));
    }
    sort (opt[u].begin(),opt[u].end(),greater<ii>());
    for(; opt[u].size() > B ; opt[u].pop_back());

    return  1;
}
int cal(int u)  {
    if (vis[u]) return  len[u];

    len[u] = (ban[u] ? -N : 0);
    vis[u] = 1;

    for(int v : g[u])
        len[u] = max(len[u],cal(v) + 1);

    return  len[u];
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;
    int q;  cin >> q;

    FOR(i,0,m)  {
        int x;  cin >> x;
        int y;  cin >> y;
        g[y].pb(x);
    }
    FOR(i,1,n + 1)  if(!vis[i]) dfs(i);
    FOR(i,1,q + 1)  {
        int u;  cin >> u;
        int k;  cin >> k;

        vector<int> vv;

        FOR(i,0,k)  {
            int x;  cin >> x;
            ban[x] = 1;
            vv.pb(x);
        }

        int ans = -1;

        if (k < B)  {
            for(ii  e : opt[u])
            if(!ban[e.Y])
                ans = max(ans,e.X);
        }
        else    {
            fill(vis + 1,vis + 1 + n,0);
            ans = max(ans,cal(u));
        }
        for(int x : vv)
            ban[x] = 0;

        cout << ans << "\n";
    }
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/

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