Submission #185418

#	Time	Username	Problem	Language	Result	Execution time	Memory
185418		Akashi	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2044 ms	227576 KiB

bitaro

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

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

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];
set <pair <int, int> > s;

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){
        s.clear();
        for(auto it : v[i])
            h[it] = max(h[it], h[i] + 1);

        s.insert({0, i});
        for(auto it : vt[i]){
            for(int k = 1; k <= K ; ++k){
                if(d[it][k].first == -1) break ;
                if(s.find({d[it][k].first + 1, d[it][k].second}) != s.end()) continue ;

                if(s.size() < K) s.insert({d[it][k].first + 1, d[it][k].second});
                else{
                    if(s.begin()->first < d[it][k].first + 1){
                        s.erase(s.begin());
                        s.insert({d[it][k].first + 1, d[it][k].second});
                    }
                    else break ;
                }
            }
        }

        set <pair <int, int> > :: reverse_iterator it = s.rbegin();
        for(int k = 1; k <= K && it != s.rend() ; ++k, ++it) d[i][k] = *it;
    }

    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;
            for(int i = 1; i <= x ; ++i) dist[i] = -300000000;
            dist[x] = 0;
            for(int i = x; i >= 1 ; --i){
                for(auto it : vt[i]) dist[it] = max(dist[it], dist[i] + 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:16: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:24: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:56: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:58: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: 0 / 7
• Subtask 3: 0 / 86