Submission #1110225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110225		Icelast	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1092 ms	428104 KiB

bitaro

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
void solve(){
    int n, m, q;
    int B = 400;
    cin >> n >> m >> q;
    vector<vector<int>> adj(n+1);
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        if(u < v) swap(u, v);
        adj[u].push_back(v);
    }
    auto heavy = [&](int T, vector<int> c) -> int{
        vector<bool> ban(n+1, false);
        for(int i : c) ban[i] = true;
        vector<int> dist(n+1, -INF);
        for(int i = 1; i <= n; i++){
            if(!ban[i]) dist[i] = 0;
            for(int j : adj[i]){
                dist[i] = max(dist[i], dist[j]+1);
            }
        }
        int res = dist[T];
        if(res < 0) res = -1;
        return res;
    };
    vector<vector<pair<int, int>>> f(n+1);
    auto precompute_for_light = [&](){
        vector<bool> d(n+1, false);
        auto merge = [&](vector<pair<int, int>> a, vector<pair<int, int>> b) -> vector<pair<int, int>>{
            vector<pair<int, int>> res;
            for(auto &it : b) it.first++;
            int n = a.size(), m = b.size();
            int j = 0;
            for(int i = 0; i < n; i++){
                while(j < m && b[j].first > a[i].first){
                    if(!d[b[j].second]){
                        res.push_back(b[j]);
                        d[b[j].second] = true;
                    }
                    j++;
                }
                if(!d[a[i].second]){
                    res.push_back(a[i]);
                    d[a[i].second] = true;
                }
            }
            while(j < m){
                if(!d[b[j].second]){
                    res.push_back(b[j]);
                    d[b[j].second] = true;
                }
                j++;
            }
            while(res.size() > B+1) res.pop_back();
            for(auto it : a) d[it.second] = false;
            for(auto it : b) d[it.second] = false;
            return res;
        };
        for(int i = 1; i <= n; i++){
            f[i].push_back({0, i});
            for(int j : adj[i]){
                f[i] = merge(f[i], f[j]);
            }
        }
    };
    precompute_for_light();
    vector<bool> ban(n+1, false);
    auto light = [&](int T, vector<int> c) -> int{
        for(int i : c) ban[i] = true;
        int res = -1;
        for(auto it : f[T]){
            if(!ban[it.second]){
                res = it.first;
                break;
            }
        }
        for(int i : c) ban[i] = false;
        return res;
    };
    for(int i = 1; i <= q; i++){
        int T, y;
        cin >> T >> y;
        vector<int> c(y);
        for(int i = 0; i < y; i++){
            cin >> c[i];
        }
        int res;
        if(y <= B){
            res = light(T, c);
        }else{
            res = heavy(T, c);
        }
        cout << res << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

bitaro.cpp: In lambda function:
bitaro.cpp:59:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             while(res.size() > B+1) res.pop_back();
      |                   ~~~~~~~~~~~^~~~~

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