Submission #1010261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010261		phong	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	695 ms	128284 KiB

bitaro

#include<bits/stdc++.h>

#define ll long long
const int nmax = 1e5 + 5, N = 3e5 + 5;
const ll oo = 1e18;
const int lg = 18, M = 4e3;
const int base = 2e5, mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;


vector<int> adj[nmax];
vector<pii> gg[nmax];
int n, m, q;
bool vis[nmax], c[nmax];
int dp[nmax];
int res[nmax], a[nmax];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//        freopen("code.inp", "r", stdin);
//        freopen("code.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1, u, v; i <= m; ++i){
        cin >> u >> v;
        adj[v].push_back(u);
    }
    int S = 90;
    vector<pii> tmp;
    for(int i = 1; i <= n; ++i){
        tmp.clear();
        gg[i].push_back({0, i});
        for(auto v : adj[i]){
            for(auto [d, x] : gg[v]){
                tmp.push_back({d + 1, x});
                res[x] = max(res[x], d + 1);
            }
        }
        for(auto [d, x] : tmp){
            if(res[x] == d){
                gg[i].push_back({d, x});
                res[x] = 0;
            }
        }
        sort(gg[i].begin(), gg[i].end(), [](pii a, pii b){
             return a.fi > b.fi;
             });
        while(gg[i].size() > S) gg[i].pop_back();
//        for(auto [d, x] : gg[i]) cout << x << ' ';
//        cout << endl;
    }


    while(q--){
        int t, y;
        cin >> t >> y;
        for(int i = 1, x; i <= y; ++i) cin >> a[i], c[a[i]] = 1;
        if(y >= S){
            for(int i = 1; i <= n; ++i) dp[i] = -n;
            dp[t] = 0;
            for(int i = t; i >= 1; --i){
                for(auto v : adj[i]){
                    dp[v] = max(dp[v], dp[i] + 1);
                }
            }
            int ans = -1;
            for(int i = 1; i <= t; ++i){
                if(c[i]) continue;
                ans = max(ans, dp[i]);
            }
            for(int i = 1; i <= n; ++i)dp[i]= 0;
            cout << ans << endl;
        }
        else{
            bool ok = 0;
            for(auto [d, x] : gg[t]){
                if(c[x]) continue;
                cout << d << endl;
                ok = 1;
                break;
            }
            if(!ok) cout << -1 << endl;

        }
        for(int i = 1; i <= y; ++i) c[a[i]] = 0;

    }
}
/*


*/

Compilation message (stderr)

bitaro.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:52:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         while(gg[i].size() > S) gg[i].pop_back();
      |               ~~~~~~~~~~~~~^~~
bitaro.cpp:61:24: warning: unused variable 'x' [-Wunused-variable]
   61 |         for(int i = 1, x; i <= y; ++i) cin >> a[i], c[a[i]] = 1;
      |                        ^

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