Submission #776472

#	Time	Username	Problem	Language	Result	Execution time	Memory
776472		taitruong270	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1128 ms	215004 KiB

bitaro

/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
I hated every minute of training, but I said, ‘Don’t quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
                                          Noi dau + Suy ngam = Tien bo 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const ll mod = 1e9+7;
ll n, m, q, dp[100005], sq=150, qry[100005], vis[100005];
vector<ll> adj[100005];
vector<pair<ll, ll>> d[100005];
 
void solve()
{
    cin>>n>>m>>q;
    for (ll i=0; i<m; i++)
    {
        ll u, v; cin>>u>>v;
        adj[v].push_back(u);
    }
    for (ll i=1; i<=n; i++)
    {
        vector<ll> candidates;
        for (ll u: adj[i]) 
        {
            for (auto [w, x]: d[u])
            {
                if (vis[x]!=i)
                {
                    candidates.push_back(x);
                    dp[x]=w+1;
                    vis[x]=i;
                }
                else dp[x]=max(dp[x], w+1);
            }
        }
        candidates.push_back(i);
        dp[i]=0;
        vector<pair<ll, ll>> dist;
        for (auto u: candidates) dist.push_back({dp[u], u});
        sort(dist.begin(), dist.end(), greater<pair<ll, ll>>());
        for (ll j=0; j<min((ll)dist.size(), sq); j++) d[i].push_back(dist[j]);
    }

    for (ll k=1; k<=q; k++)
    {
        ll z; cin>>z;
        ll cnt; cin>>cnt;
        for (ll i=0; i<cnt; i++)
        {
            ll x; cin>>x;
            qry[x]=k;
        }
        if (cnt<sq)
        {
            ll ans=-1;
            for (auto [w, v]: d[z]) if (qry[v]!=k)
            {
                ans=w;
                break;
            }
            cout<<ans<<endl;
        }
        else 
        {
            for (ll i=1; i<=n; i++) dp[i]=-1;
            for (ll i=1; i<=n; i++) if (qry[i]!=k) 
                dp[i]=0;
            for (ll i=1; i<=n; i++) 
                for (ll v: adj[i]) if (dp[v]!=-1) dp[i]=max(dp[i], dp[v]+1);
            cout<<dp[z]<<endl;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

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