Submission #1265232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265232		nguyenhuythach	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2 ms	4932 KiB

bitaro

#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 int long long
#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];

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(const vector<pii> &a, const vector<pii> &b) {
    vector<pii> c;
    c.reserve(min<size_t>(block, a.size() + b.size()));
    int pta = 0, ptb = 0;
    vector<int> used; used.reserve(block + 5); // lưu id đã tăng cnt

    auto mark = [&](int id){
        if (cnt[id] == 0) used.push_back(id); // chỉ thêm lần đầu trong merge này
        cnt[id]++;
    };

    while (pta < (int)a.size() && ptb < (int)b.size() && (int)c.size() < block) {
        if (a[pta] > b[ptb]) {
            if (!cnt[a[pta].second]) c.push_back(a[pta]);
            mark(a[pta].second);
            ++pta;
        } else {
            if (!cnt[b[ptb].second]) c.push_back(b[ptb]);
            mark(b[ptb].second);
            ++ptb;
        }
    }
    while (pta < (int)a.size() && (int)c.size() < block) {
        if (!cnt[a[pta].second]) c.push_back(a[pta]);
        mark(a[pta].second);
        ++pta;
    }
    while (ptb < (int)b.size() && (int)c.size() < block) {
        if (!cnt[b[ptb].second]) c.push_back(b[ptb]);
        mark(b[ptb].second);
        ++ptb;
    }

    // reset tất cả id đã tăng cnt trong lần merge này
    for (int id : used) cnt[id] = 0;
    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)
{
    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();
//    FOR(i,1,n) { FORD(j,save[i]) cout << j.fi << ' '; cout << '\n'; }
    while(q--)
    {
        int t,y; cin >> t >> y;
        FOR(i,1,n) ans[i]=0;
        FOR(i,1,y)
        {
            int x; cin >> x;
            ans[x]=-1;
        }
        
        if(y<=block)
        {
            FORD(i,save[t])
            {
                if(ans[i.se]!=-1)
                {
                    cout << i.fi << '\n';
                    break;
                }
            }
        }
        else
        {
            dfs(t,0);
            cout << ans[t] << '\n';
        }
    }
}

signed 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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86