Submission #1346524

#TimeUsernameProblemLanguageResultExecution timeMemory
1346524tuanvn2009Bitaro’s Party (JOI18_bitaro)C++20
0 / 100
2093 ms1348 KiB
#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

#include <cmath>

const int maxn = 1e5 + 3, maxs = sqrt(maxn / __lg(maxn)) + 1;

struct Path {
    int v, dist;
};

vector<int> g[maxn], invalids;
vector<Path> topK[maxn];

bool visit[maxn], exist[maxn];
int dist[maxn];

void dfs(int u) {
    if (visit[u]) {
        return;
    }
    
    topK[u] = {{u, 0}};
    visit[u] = true;
    
    for (int &v : g[u]) {
        if (!visit[v]) dfs(v);
        auto a = topK[u], b = topK[v];
        
        for (auto &path : a) exist[path.v] = false;
        for (auto &path : b) exist[path.v] = false;
        
        topK[u].resize(0);
        
        while (topK[u].size() < maxs) {
            Path curA = {-1, -1}, curB = {-1, -1};
            
            while (a.size() && exist[a.back().v]) a.pop_back();
            while (b.size() && exist[b.back().v]) b.pop_back();
            
            if (a.size()) curA = a.back();
            if (b.size()) curB = b.back();
            
            if (curA.dist < ++curB.dist) swap(curA, curB);
            if (curA.v < 0) break;
            
            topK[u].push_back(curA);
            exist[topK[u].back().v] = true;
        }
        
        reverse(begin(topK[u]), end(topK[u]));
    }
}

int maxDist(int u) {
    int res = dist[u];
    
    if (binary_search(begin(invalids), end(invalids), u)) {
        res = -1;
    }
    
    for (int &v : g[u]) {
        dist[v] = dist[u] + 1;
        res = max(res, maxDist(v));
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, q; cin >> n >> m >> q;
    
    while (m--) {
        int u, v; cin >> u >> v;
        if (u < v) swap(u, v);
        
        g[u].push_back(v);
    }
    
    for (int i = 1; i <= n; ++i) dfs(i);
    for (auto &u : topK) reverse(begin(u), end(u));
    
    while (q--) {
        int t, y; cin >> t >> y;
        
        invalids.resize(y);
        for (int &u : invalids) cin >> u;
        
        if (y < maxs) for (auto &cur : topK[t]) {
            if (!binary_search(begin(invalids), end(invalids), cur.v)) {
                cout << cur.dist << '\n';
                goto skip;
            }
        } else {
            dist[t] = 0;
            
            cout << maxDist(t) << '\n';
            goto skip;
        }
        
        cout << -1 << '\n';
        skip: true;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...