Submission #166258

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

const int LEN = 1 << 14;
char buff[LEN];
int ind = LEN - 1;

int i32(){
    int ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + (buff[ind] - '0');
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    return ans;
}

int main(){

    n = i32();
    m = i32();
    q = i32();

    for(int i = 1;i <= m;i++){
        int x,y;
        x = i32();
        y = i32();
        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((int)tmp.size() < BUCK && (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++;
                }
            }
            cache[i] = tmp;
        }
    }

    while(q--){
        int town,sz;

        town = i32();
        sz = i32();

        for(int i = 1;i <= sz;i++){
            int val;
            val = i32();
            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 i32()':
bitaro.cpp:38:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:46:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~

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