Submission #535768

#	Time	Username	Problem	Language	Result	Execution time	Memory
535768		79brue	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1499 ms	220028 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define LIM 250

using namespace std;

typedef long long ll;

int n, m, q;
vector<pair<int, int> > vec[100002];
vector<int> link[100002];
vector<int> revLink[100002];

bool chk[100002];
int DP[100002];
int ans;

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        revLink[y].push_back(x);
    }

    for(int i=1; i<=n; i++){
        if(revLink[i].empty()){
            vec[i].push_back(make_pair(i, 0));
            continue;
        }

        vector<pair<int, int> > va, vb, vret;
        va.push_back(make_pair(i, 0));
        for(auto prv: revLink[i]){
            vb = vec[prv];
            for(auto &val: vb) val.second++;

            vret.clear();
            int vaPnt = 0, vbPnt = 0;
            while(vaPnt < (int)va.size() && vbPnt < (int)vb.size() && (int)vret.size() <= LIM){
                if(chk[va[vaPnt].first]) vaPnt++;
                else if(chk[vb[vbPnt].first]) vbPnt++;
                else if(va[vaPnt].second > vb[vbPnt].second) chk[va[vaPnt].first] = 1, vret.push_back(va[vaPnt++]);
                else chk[vb[vbPnt].first] = 1, vret.push_back(vb[vbPnt++]);
            }
            while(vaPnt < (int)va.size() && (int)vret.size() <= LIM){
                if(chk[va[vaPnt].first]) vaPnt++;
                else chk[va[vaPnt].first] = 1, vret.push_back(va[vaPnt++]);
            }
            while(vbPnt < (int)vb.size() && (int)vret.size() <= LIM){
                if(chk[vb[vbPnt].first]) vaPnt++;
                else chk[vb[vbPnt].first] = 1, vret.push_back(vb[vbPnt++]);
            }
            for(auto p: vret) chk[p.first] = 0;
            va.swap(vret);
        }
        vec[i].swap(va);
    }

    for(int i=1; i<=q; i++){
        int t, y; vector<int> lst;
        scanf("%d %d", &t, &y);
        for(int i=0; i<y; i++){
            int tmpx;
            scanf("%d", &tmpx);
            lst.push_back(tmpx);
        }

        if(y <= LIM){
            for(auto x: lst) chk[x] = 1;
            int ans = -1;
            for(auto x: vec[t]){
                if(chk[x.first]) continue;
                ans = x.second;
                break;
            }
            printf("%d\n", ans);
            for(auto x: lst) chk[x] = 0;
        }
        else{
            for(auto x: lst) chk[x] = 1;
            for(int i=1; i<=n; i++) DP[i] = -1e9;
            DP[t] = 0;
            ans = -1;

            for(int i=t; i>=1; i--){
                for(auto y: link[i]) DP[i] = max(DP[i], DP[y]+1);
                if(!chk[i]) ans = max(ans, DP[i]);
            }
            printf("%d\n", ans);
            for(auto x: lst) chk[x] = 0;
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d %d", &t, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |             scanf("%d", &tmpx);
      |             ~~~~~^~~~~~~~~~~~~

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