Submission #1135950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135950		byunjaewoo	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	732 ms	262304 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, sqrtN=80, INF=1e18;
int n, m, q, d[N], mx[N];
bool chk[N];
vector<pair<int, int>> v[N];
vector<int> adj[N];

signed main() {
    scanf("%lld%lld%lld", &n, &m, &q);
    for(int i=1; i<=m; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        adj[v].push_back(u);
    }
    for(int i=1; i<=n; i++) {
        for(int j:adj[i]) {
            vector<pair<int, int>> tmp;
            for(int p=0, q=0, k=0; k<sqrtN && (p<v[i].size() || q<v[j].size()); k++) {
                if(p==v[i].size() || (q<v[j].size() && v[i][p].first<v[j][q].first+1)) {
                    if(chk[v[j][q].second]) {
                        q++, k--; continue;
                    }
                    chk[v[j][q].second]=true, tmp.push_back({v[j][q].first+1, v[j][q].second});
                    q++;
                }
                else {
                    if(chk[v[i][p].second]) {
                        p++, k--; continue;
                    }
                    chk[v[i][p].second]=true, tmp.push_back({v[i][p].first, v[i][p].second});
                    p++;
                }
            }
            v[i]=tmp;
            for(auto i:tmp) chk[i.second]=false;
        }
        v[i].push_back({0, i});
    }
    while(q--) {
        int x, y; cin>>x>>y;
        vector<int> tv;
        for(int i=1; i<=y; i++) {
            int t; cin>>t;
            if(t<=x) tv.push_back(t), chk[t]=true;
        }
        y=tv.size();
        if(y>=sqrtN) {
            fill(d+1, d+x+1, -INF);
            for(int i=1; i<=x; i++) {
                if(!chk[i]) d[i]=0;
                for(int j:adj[i]) d[i]=max(d[i], d[j]+1);
            }
            printf("%lld\n", max(-1ll, d[x]));
        }
        else {
            int ans=-1;
            for(int i=0; i<v[x].size(); i++) {
                if(chk[v[x][i].second]) continue;
                ans=v[x][i].first; break;
            }
            printf("%lld\n", ans);
        }
        for(int i:tv) chk[i]=false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%lld%lld%lld", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:14:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         int u, v; scanf("%lld%lld", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~

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