제출 #1265240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265240		nguyenhuythach	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	1120 ms	423324 KiB

bitaro

#include<iostream>// #include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1e5+69;
const int block=320;
int n,m,q;
vector<int> adj[nmax];
vector<pii> save[nmax];
int ans[nmax],vst[nmax],cnt[nmax];
vector<int> lol;
int visit[nmax];

void input()
{
    cin >> n >> m >> q;
    FOR(i,1,m)
    {
        int u,v; cin >> u >> v;
        adj[max(u,v)].push_back(min(u,v));
    }
}

vector<pii> merge(vector<pii> &a,vector<pii> &b)
{
    vector<pii> c;
    int pta=0,ptb=0;
    while(pta<sz(a) && ptb<sz(b))
    {
        if(a[pta]>b[ptb])
        {
            if(!cnt[a[pta].se]) c.push_back(a[pta]);
            cnt[a[pta].se]++;
            pta++;
        }
        else
        {
            if(!cnt[b[ptb].se]) c.push_back(b[ptb]);
            cnt[b[ptb].se]++;
            ptb++;
        }
    }
    FOR(i,pta,sz(a)-1) 
    {
        if(!cnt[a[i].se]) c.push_back(a[i]);
        cnt[a[i].se]++;
    }
    FOR(i,ptb,sz(b)-1) 
    {
        if(!cnt[b[i].se]) c.push_back(b[i]);
        cnt[b[i].se]++;
    }
    FORD(i,c) cnt[i.se]=0;
    while(sz(c)>block) c.pop_back();
    return c;
}

void pre_dfs(int u,int v)
{
    vst[u]=true;
    FORD(i,adj[u])
    {
        if(i==v) continue;
        if(!vst[i]) pre_dfs(i,u);
        FOR(j,0,sz(save[i])-1) save[i][j].fi++;
        save[u]=merge(save[u],save[i]);
        FOR(j,0,sz(save[i])-1) save[i][j].fi--;
    }
}

void build()
{
    FOR(i,1,n) save[i].push_back({0,i});
    REP(i,n,1) if(!vst[i]) pre_dfs(i,0);
}

void dfs(int u,int v)
{
    if(visit[u]) return;
    visit[u] = 1;
    lol.push_back(u);

    FORD(i,adj[u])
    {
        if(i==v) continue;
        dfs(i,u);
        if(ans[i]!=-1) ans[u]=max(ans[u],ans[i]+1);
    }
}

void solve()
{
    build();
    while(q--)
    {
        int t,y; cin >> t >> y;
        FOR(i,1,y)
        {
            int x; cin >> x;
            lol.push_back(x);
            ans[x]=-1;
        }
        
        if(y<=block)
        {
            bool flag=false;
            FORD(i,save[t])
            {
                if(ans[i.se]!=-1)
                {
                    cout << i.fi << '\n';
                    flag=true;
                    break;
                }
            }
            if(!flag) cout << -1 << '\n';
        }
        else
        {
            dfs(t,0);
            cout << ans[t] << '\n';
        }
        
        FORD(i,lol) { ans[i]=0; visit[i]=0; }
        lol.clear();
    }
}

int main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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