제출 #1103441

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

bitaro

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int nx=1e5+5;
const int bl=317;
int n, m, q, tmp[nx], d[nx];
vector<int> adj[nx];
vector<ii> best[nx];
bool ok[nx];
queue<int> f;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    while(m--)
    {
        int u, v;
        cin>>u>>v;
        adj[v].emplace_back(u);
    }
    memset(tmp, -1, sizeof(tmp));
    for(int u = 1; u <= n; u++)
    {
        vector<int> cur;
        best[u].emplace_back(0, u);
        for(int v:adj[u])
        {
            for(auto it:best[v])
            {
                int c=it.se, w=it.fi;
                if(tmp[c]==-1)
                    tmp[c]=w+1, cur.emplace_back(c);
                else tmp[c]=max(tmp[c], w+1);
            }
        }
        for(int v:cur)
        {
            best[u].emplace_back(tmp[v], v);
            tmp[v]=-1;
        }
        sort(best[u].begin(), best[u].end(), greater<ii>());
        while(best[u].size()>bl)
            best[u].pop_back();
    }
    while(q--)
    {
        int t, y, ans=-1;
        vector<int> a;
        cin>>t>>y;
        a.resize(y);
        for(int i = 0; i < y; i++)
            cin>>a[i], ok[a[i]]=1;
        if(y<bl)
        {
            for(auto it:best[t])
            {
                if(ok[it.se])
                    continue;
                ans=it.fi;
                break;
            }
        }
        else
        {
            for(int i = 1; i <= n; i++)
                d[i]=-1;
            d[t]=0;
            f.push(t);
            while(f.size())
            {
                int u=f.front();
                f.pop();
                for(int v:adj[u])
                    if(d[v]==-1)
                        d[v]=d[u]+1, f.push(v);
            }
            for(int i = 1; i <= n; i++)
                if(d[i]!=-1)
                    ans=max(ans, d[i]);
        }
        for(int i = 0; i < y; i++)
            ok[a[i]]=0;
        cout<<ans<<'\n';
    }
}

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