Submission #1109555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109555		tinnhiemnn	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1452 ms	146108 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define file "test"
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
const int N=1e5+2;
int n,m,q,dp[N];
vector<int> E[N];
vector<pii> f[N];

int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m>>q;
    for (int i=1;i<=m;i++)
    {
        int u,v; cin>>u>>v; E[v].pb(u);
    }

    for (int i=1;i<=n;i++)
    {
        f[i].pb({0, i});
        vector<int> tmp, dis(n+1, -1);

        for (int j : E[i]) for (pii p : f[j])
        {
            int u=p.second, w=p.first;
            if (dis[u] == -1)
            {
                tmp.pb(u); dis[u]=w+1;
            }
            else dis[u]=max(dis[u], w+1);
        }

        for (int u : tmp) f[i].pb({dis[u], u});
        sort(f[i].rbegin(), f[i].rend());

        while (f[i].size() > 100) f[i].pop_back();
    }


    while (q--)
    {
        int t,k; cin>>t>>k;
        vector<bool> ok(n+1, 0); for (int i=1;i<=k;i++) {int x; cin>>x; ok[x]=1;}

        if (k >= 100)
        {
            int res=-1;
            for (int i=t;i>=1;i--) dp[i]=-1; dp[t]=0;
            for (int i=t;i>=1;i--)
            {
                if (dp[i]<0) continue;
                if (!ok[i]) res=max(res, dp[i]);
                for (int v : E[i]) dp[v]=max(dp[v], dp[i]+1);
            }

            cout<<res<<'\n';
        }
        else {
            int res=-1;
            for (pii p : f[t]) if (!ok[p.second]) {res=p.first; break;}
            cout<<res<<'\n';
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:57:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |             for (int i=t;i>=1;i--) dp[i]=-1; dp[t]=0;
      |             ^~~
bitaro.cpp:57:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   57 |             for (int i=t;i>=1;i--) dp[i]=-1; dp[t]=0;
      |                                              ^~

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