Submission #390494

#	Time	Username	Problem	Language	Result	Execution time	Memory
390494		iANikzad	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1863 ms	420424 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQRT = 400;

vector<int> adj[maxn], rev[maxn];

int id[maxn], dp[maxn];
bool mark[maxn];

vector<pii> res[maxn];

int32_t main()
{
    FAST;

    int n, m, qq;
    cin >> n >> m >> qq;

    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        adj[u].pb(v);
        rev[v].pb(u);
    }

    stack<int> st;

    for(int u = 1; u <= n; u++)
    {
        for(int v : rev[u]) id[v] = 0;
        for(int i = 0; i < SQRT; i++)
        {
            pii mx = {u, 0};
            for(int v : rev[u])
            {
                while(id[v] < res[v].size() && mark[res[v][id[v]].F])
                    id[v]++;

                if(id[v] < res[v].size() && res[v][id[v]].S + 1 > mx.S)
                    mx = {res[v][id[v]].F, res[v][id[v]].S + 1};
            }

            res[u].pb(mx);
            mark[mx.F] = true;
            st.push(mx.F);

            if(mx.F == u) break;
            else id[mx.F]++;
        }

        while(!st.empty()) mark[st.top()] = false, st.pop();
    }

    while(qq--)
    {
        int T, Y;
        cin >> T >> Y;

        for(int i = 0; i < Y; i++)
        {
            int x; cin >> x;
            mark[x] = true;

            st.push(x);
        }

        if(Y >= SQRT)
        {
            for(int i = 1; i <= n; i++) dp[i] = -INF;
            dp[T] = 0;

            int ans = -1;
            if(!mark[T]) ans = 0;

            for(int i = T-1; i >= 1; i--)
            {
                for(int v : adj[i])  dp[i] = max(dp[i], dp[v] + 1);
                if(!mark[i]) ans = max(ans, dp[i]);
            }

            cout << ans << "\n";
        }
        else
        {
            int ans = -1;
            for(pii p : res[T])
            {
                int v = p.F;
                int w = p.S;

                if(!mark[v]) {
                    ans = w;
                    break;
                }
            }

            cout << ans << "\n";
        }

        while(!st.empty()) mark[st.top()] = false,st.pop();
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:56:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 while(id[v] < res[v].size() && mark[res[v][id[v]].F])
      |                       ~~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 if(id[v] < res[v].size() && res[v][id[v]].S + 1 > mx.S)
      |                    ~~~~~~^~~~~~~~~~~~~~~

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