Submission #166237

#	Time	Username	Problem	Language	Result	Execution time	Memory
166237		georgerapeanu	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	2047 ms	275576 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;
}

void merge_caches(vector<pair<int,int> > s,vector<pair<int,int> > &t){
    for(auto &it:s){
        it.first++;
    }
    vector<pair<int,int> > tmp = vector<pair<int,int> > ((s.size() + t.size()));
    merge(s.begin(),s.end(),t.begin(),t.end(),tmp.begin(),cmp);
    tmp.resize(min((int)tmp.size(),BUCK));
    swap(tmp,t);
}

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

int dp[NMAX + 5];

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]){
            merge_caches(cache[it],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:38: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:42: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:55: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:59: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