Submission #166239

#	Time	Username	Problem	Language	Result	Execution time	Memory
166239		georgerapeanu	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2092 ms	368280 KiB

bitaro

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;
const int MMAX = 2e5;
const int QMAX = 1e5;
const int BUCK = 200;

int n,m;
int q;
vector<int> graph[NMAX + 5];
vector<pair<int,int> > cache[NMAX + 5];

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first > b.first;
}

bool banned[NMAX + 5];
vector<int> list;

int dp[NMAX + 5];

vector<pair<int,int> > tmp;

int main(){

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

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

    for(int i = 1;i <= n;i++){
        cache[i].push_back({0,i});
        for(auto it:graph[i]){
            tmp.clear();
            int x = 0;
            int y = 0;

            while(x < (int)cache[it].size() || y < (int)cache[i].size()){
                if(x < (int)cache[it].size() && (y == (int)cache[i].size() || cache[it][x].first + 1 >= cache[i][y].first)){
                    tmp.push_back({cache[it][x].first + 1,cache[it][x].second});
                    x++;
                }
                else{
                    tmp.push_back(cache[i][y]);
                    y++;
                }
            }
            tmp.resize(min(BUCK,(int)tmp.size()));
            swap(tmp,cache[i]);
        }
    }

    while(q--){
        int town,sz;
        scanf("%d %d",&town,&sz);

        for(int i = 1;i <= sz;i++){
            int val;
            scanf("%d",&val);
            list.push_back(val);
            banned[val] = true;
        }

        bool ok = false;

        for(auto it:cache[town]){
            if(banned[it.second]){
                continue;
            }
            printf("%d\n",it.first);
            ok = true;
            break;
        }

        if(ok == false){
            for(int i = 1;i <= town;i++){
                dp[i] = (banned[i] ? -1e9:0);
                for(auto it:graph[i]){
                    dp[i] = max(dp[i],dp[it] + 1);
                }
            }
            printf("%d\n",(dp[town] < 0 ? -1:dp[town]));
        }

        for(auto it:list){
            banned[it] = false;
        }
        list.clear();
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:30: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:34: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:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&town,&sz);
         ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&val);
             ~~~~~^~~~~~~~~~~

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