제출 #1160331

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

bitaro

// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define     pii     pair<int,int>

const int mxN = 1e5+7 , T = 32;
int n,m,q , f[mxN]; bool mrk[mxN];
set<pii , greater<pii>> bitaro[mxN];
vector<int> e[mxN],que;

void iN ()
{
    cin >> n >> m >> q;
    for (int i=1; i<=m; i++)
    {
        int u,v; cin >> u >> v;
        if (u > v) swap(u , v);
        e[u].push_back(v);
    }
}

void preprocess ()
{
    for (int i=1; i<=n; i++)
        bitaro[i].insert({0 , i});
    bool vis[mxN];
    memset(vis , 0 , sizeof(vis));
    for (int v=1; v<=n; v++)
    {
        set<pii,greater<pii>> update;
        int sz = 0;
        for (auto [k , p] : bitaro[v])
        {
            if (sz >= T) break;
            if (vis[p]) continue;
            update.insert({k , p});
            vis[p] = true; sz++;
        }
        bitaro[v] = update;
        for (auto [k , p] : update)
            vis[p] = 0;
        for (auto to : e[v])
            for (auto [k , p] : bitaro[v])
                bitaro[to].insert({k+1 , p});
    }
}

inline void reset ()
{
    for (auto v : que) mrk[v] = 0;
    que.clear();
}

int light (int o , int sz)
{
    for (auto v : que) mrk[v] = 1;
    for (auto [len,v] : bitaro[o])
        if (!mrk[v])
        {
            reset();
            return len;
        }
    reset();
    return -1;
}

int heavy (int o , int sz)
{
    fill_n(f , o+1 , 0);
    for (auto v : que)
        f[v] = -mxN;
    
    for (int v=1; v<=o; v++)
        for (auto to : e[v])
            f[to] = max(f[to] , f[v]+1);
    
    que.clear();
    if (f[o] < 0) return -1;
    else return f[o];
}

void ouT ()
{
    while (q--)
    {
        int v,sz; cin >> v >> sz;
        for (int i=1 , x; i<=sz; i++)
            cin >> x , que.push_back(x);
        
        if (sz < T) cout << light (v , sz) << '\n';
        else cout << heavy (v , sz) << '\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    
    iN ();
    preprocess ();
    ouT ();
}

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