Submission #185426

#	Time	Username	Problem	Language	Result	Execution time	Memory
185426		Akashi	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1272 ms	177088 KiB

bitaro

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

const int N = 1e5;
const int K = 200;

int n, m, q;
bool viz[N + 5];
int h[N + 5], a[N + 5], dist[N + 5];
pair <int, int> d[N + 5][K + 5];
vector <int> v[N + 5], vt[N + 5];
vector <int> aux;

inline bool cmp(int x, int y){return dist[x] > dist[y];}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= K ; ++j)
            d[i][j] = {-1, -1};

    int x, y;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        vt[y].push_back(x);
    }

    for(int i = 1; i <= n ; ++i){
        aux.clear();
        aux.push_back(i);

        dist[0] = 0;
        for(auto it : vt[i]){
            for(int k = 1; k <= K ; ++k){
                if(d[it][k].first == -1) break ;
                int nod = d[it][k].second;
                dist[nod] = max(dist[nod], d[it][k].first + 1);
                if(!viz[nod]) viz[nod] = 1, aux.push_back(nod);
            }
        }

        sort(aux.begin(), aux.end(), cmp);
        for(int j = 1; j <= K && j <= aux.size() ; ++j) d[i][j] = {dist[aux[j - 1]], aux[j - 1]};
        for(auto it : aux) viz[it] = dist[it] = 0;
    }

    while(q--){
        scanf("%d%d", &x, &y);
        for(int i = 1; i <= y ; ++i){
            scanf("%d", &a[i]);
            viz[a[i]] = 1;
        }

        int ans = -2;
        for(int i = 1; i <= K ; ++i){
            if(d[x][i].first == -1) {ans = -1; break ;}
            if(!viz[d[x][i].second]) {ans = d[x][i].first; break ;}
        }

        if(ans == -2){
            ans = -1;
            dist[x] = 0;
            if(!viz[x]) ans = 0;
            for(int i = x - 1; i >= 1 ; --i){
                dist[i] = -30000000;
                for(auto it : v[i]) if(it <= x) dist[i] = max(dist[i], dist[it] + 1);
                if(!viz[i]) ans = max(dist[i], ans);
            }
        }

        printf("%d\n", ans);
        for(int i = 1; i <= y ; ++i) viz[a[i]] = 0;
    }


    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:46:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j <= K && j <= aux.size() ; ++j) d[i][j] = {dist[aux[j - 1]], aux[j - 1]};
                                  ~~^~~~~~~~~~~~~
bitaro.cpp:47:47: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         for(auto it : aux) viz[it] = dist[it] = 0;
                                      ~~~~~~~~~^~~
bitaro.cpp:18: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:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:53:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
             ~~~~~^~~~~~~~~~~~~

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