Submission #1103451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103451		danglayloi1	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	647 ms	143432 KiB

bitaro

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int nx=1e5+5;
int n, m, q, tmp[nx], d[nx], bl;
vector<int> adj[nx];
vector<ii> best[nx];
bool ok[nx];
queue<int> f;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    bl=100;
    while(m--)
    {
        int u, v;
        cin>>u>>v;
        adj[v].emplace_back(u);
    }
    memset(tmp, -1, sizeof(tmp));
        vector<int> cur;
    for(int u = 1; u <= n; u++)
    {
        cur.clear();
        best[u].emplace_back(0, u);
        for(int &v:adj[u])
        {
            for(auto &[w, c]:best[v])
            {
                if(tmp[c]==-1)
                    tmp[c]=w+1, cur.emplace_back(c);
                else tmp[c]=max(tmp[c], w+1);
            }
        }
        for(int &v:cur)
        {
            best[u].emplace_back(tmp[v], v);
            tmp[v]=-1;
        }
        sort(best[u].begin(), best[u].end(), greater<ii>());
        while(best[u].size()>bl)
            best[u].pop_back();
    }
    while(q--)
    {
        int t, y, ans=-1;
        vector<int> a;
        cin>>t>>y;
        a.resize(y);
        for(int i = 0; i < y; i++)
            cin>>a[i], ok[a[i]]=1;
        if(y<bl)
        {
            for(auto it:best[t])
            {
                if(ok[it.se])
                    continue;
                ans=it.fi;
                break;
            }
        }
        else
        {
            for(int i = 1; i <= t; i++)
                d[i]=-1;
            d[t]=0;
            for(int i = t; i >= 1; i--)
            {
                if(d[i]==-1)
                    continue;
                for(int j:adj[i])
                    d[j]=max(d[j], d[i]+1);
            }
            for(int i = 1; i <= t; i++)
                if(d[i]!=-1 && !ok[i])
                    ans=max(ans, d[i]);
        }
        for(int i = 0; i < y; i++)
            ok[a[i]]=0;
        cout<<ans<<'\n';
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         while(best[u].size()>bl)
      |               ~~~~~~~~~~~~~~^~~

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