Submission #1103476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103476		phong	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1291 ms	255304 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;

int vis[nmax], c[nmax], 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 = 200;

    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;

        if(y >= S){

            for(int i = 1, x; i <= y; ++i) cin >> x, c[x] = 1;

            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)c[i] =dp[i]= 0;

            cout << ans << endl;

        }

        else{

            for(int i = 1,x; i <= y; ++i){

                cin >> x, c[x] = 1;

                a[i] = x;

            }

            bool ok = 0;

            for(auto [d, x] : gg[t]){

                if(c[x]) continue;

                cout << d << endl;

                ok = 1;

                break;

            }

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

            if(!ok) cout << -1 << endl;

 

        }

    }

}

/*

 

 

*/

Compilation message (stderr)

bitaro.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main(){
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:100: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]
  100 |         while(gg[i].size() > S) gg[i].pop_back();
      |               ~~~~~~~~~~~~~^~~

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