Submission #646962

#	Time	Username	Problem	Language	Result	Execution time	Memory
646962		parsadox2	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1747 ms	424704 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10 , maxsq = 400;
int n , m , q , dis[maxn];
vector <int> g[maxn] , revg[maxn] , alldis[maxn];
vector <pair<int , int>> big_path[maxn] , all;
bool marked[maxn];

void merg(int a , int b)
{
    vector <pair <int ,int> > res;
    int pa = 0 , pb = 0 , sz = 0 , sza = big_path[a].size() , szb = big_path[b].size();
    while(sz < maxsq)
    {
        if(pa == sza || pb == szb)
            break;
        if(big_path[b][pb].second >= big_path[a][pa].second)
        {
            if(!marked[big_path[b][pb].first])
            {
                marked[big_path[b][pb].first] = true;
                res.push_back(make_pair(big_path[b][pb].first , big_path[b][pb].second + 1));
                sz++;
            }
            pb++;
        }
        else
        {
            if(!marked[big_path[a][pa].first])
            {
                marked[big_path[a][pa].first] = true;
                res.push_back(make_pair(big_path[a][pa].first , big_path[a][pa].second));
                sz++;
            }
            pa++;
        }
    }
    if(sz < maxsq)
    {
        while(pa < sza)
        {
            if(sz >= maxsq)
                break;
            if(!marked[big_path[a][pa].first])
            {
                marked[big_path[a][pa].first] = true;
                res.push_back(make_pair(big_path[a][pa].first , big_path[a][pa].second));
                sz++;
            }
            pa++;
        }
        while(pb < szb)
        {
            if(sz >= maxsq)
                break;
            if(!marked[big_path[b][pb].first])
            {
                marked[big_path[b][pb].first] = true;
                res.push_back(make_pair(big_path[b][pb].first , big_path[b][pb].second + 1));
                sz++;
            }
            pb++;
        }
    }
    for(auto u : res)
        marked[u.first] = false;
    big_path[a].swap(res);
}

void find_path(int v)
{
    for(int i = 0 ; i <= n ; i++)
    {
        dis[i] = -1 ;
        alldis[i].clear();
    }
    dis[v] = 0;
    alldis[0].push_back(v);
    for(int i = v - 1 ; i > 0 ; i--)
    {
        for(auto u : g[i])
            if(dis[u] > -1)
                dis[i] = max(dis[i] , dis[u] + 1);
        alldis[dis[i]].push_back(i);
    }
    for(int i = n ; i > -1 ; i--)
        for(auto u : alldis[i])
            all.push_back(make_pair(u , i));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 0 ; i < m ; i++)
    {
        int s , e;
        cin >> s >> e;
        //s = i + 1;
        //e = i + 3;
        g[s].push_back(e);
        revg[e].push_back(s);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        big_path[i].push_back(make_pair(i , 0));
        for(auto u : revg[i])
            merg(i , u);
    }
    while(q--)
    {
        int t , y;
        cin >> t >> y;
        vector <int> bad;
        for(int i = 0 ; i < y ; i++)
        {
            int tmp;
            cin >> tmp;
            bad.push_back(tmp);
        }
        for(int i : bad)
            marked[i] = true;
        if(y < maxsq)
        {
            int ans = -1;
            for(auto i : big_path[t])
            {
                if(!marked[i.first])
                {
                    ans = i.second;
                    break;
                }
            }
            cout << ans << '\n';
            
        }
        else
        {
            all.clear();
            find_path(t);
            int ans = -1;
            for(auto u : all)
            {
                if(!marked[u.first])
                {
                    ans = u.second;
                    break;
                }
            }
            cout << ans << '\n';
        }
        for(auto i : bad)
            marked[i] = false;
    }
    return 0;
}

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