Submission #172228

#	Time	Username	Problem	Language	Result	Execution time	Memory
172228		arnold518	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1618 ms	111472 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;
const int SQ = 100;

int N, M, Q;
vector<int> adj[MAXN+10];
vector<pii> V[MAXN+10];

int T, Y, dp[MAXN+10];
int X[MAXN+10];

int main()
{
    int i, j, k;

    scanf("%d%d%d", &N, &M, &Q);
    for(i=1; i<=M; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[v].push_back(u);
    }

    for(i=1; i<=N; i++)
    {
        V[i].push_back({0, i});
        for(auto nxt : adj[i])
        {
            vector<pii> t, p, q;
            for(auto it : V[nxt]) p.push_back({it.first+1, it.second});
            q=V[i];

            V[i].clear();

            for(j=0, k=0; V[i].size()<SQ && (j<p.size() || k<q.size()); )
            {
                if(j<p.size() && (k>=q.size() || p[j].first>q[k].first))
                {
                    if(!X[p[j].second])
                    {
                        X[p[j].second]=1;
                        V[i].push_back(p[j]);
                    }
                    j++;
                }
                else
                {
                    if(!X[q[k].second])
                    {
                        X[q[k].second]=1;
                        V[i].push_back(q[k]);
                    }
                    k++;
                }
            }

            for(j=0; j<p.size(); j++) X[p[j].second]=0;
            for(k=0; k<q.size(); k++) X[q[k].second]=0;
        }
        //printf("%d : ", i);
        //for(auto it : V[i]) printf("(%d %d) ", it.first, it.second);
        //printf("\n");
    }

    for(i=1; i<=Q; i++)
    {
        scanf("%d%d", &T, &Y);
        vector<int> p;

        for(j=1; j<=Y; j++)
        {
            int t;
            scanf("%d", &t);
            p.push_back(t);
            X[t]=1;
        }
        if(Y>=SQ)
        {
            for(j=1; j<=N; j++) dp[j]=-987654321;
            dp[T]=0;
            int ans=-1;
            for(j=T; j>=1; j--)
            {
                if(!X[j]) ans=max(ans, dp[j]);
                for(auto nxt : adj[j]) dp[nxt]=max(dp[nxt], dp[j]+1);
            }
            printf("%d\n", ans);
        }
        else
        {
            int ans=-1;
            for(auto it : V[T])
            {
                if(X[it.second]) continue;
                ans=it.first;
                break;
            }
            printf("%d\n", ans);
        }

        for(auto it : p) X[it]=0;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:42:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0, k=0; V[i].size()<SQ && (j<p.size() || k<q.size()); )
                                              ~^~~~~~~~~
bitaro.cpp:42:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0, k=0; V[i].size()<SQ && (j<p.size() || k<q.size()); )
                                                            ~^~~~~~~~~
bitaro.cpp:44:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j<p.size() && (k>=q.size() || p[j].first>q[k].first))
                    ~^~~~~~~~~
bitaro.cpp:44:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(j<p.size() && (k>=q.size() || p[j].first>q[k].first))
                                   ~^~~~~~~~~~
bitaro.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(j=0; j<p.size(); j++) X[p[j].second]=0;
                      ~^~~~~~~~~
bitaro.cpp:65:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(k=0; k<q.size(); k++) X[q[k].second]=0;
                      ~^~~~~~~~~
bitaro.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &T, &Y);
         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &t);
             ~~~~~^~~~~~~~~~

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