Submission #1346734

#TimeUsernameProblemLanguageResultExecution timeMemory
1346734tuanvn2009Bitaro’s Party (JOI18_bitaro)C++17
0 / 100
2052 ms5456 KiB
#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

#include <cmath>

const int maxn = 1e5 + 3;

struct Path {
    int v, dist;
};

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

bool visit[maxn], exist[maxn], invalid[maxn];
int dist[maxn], maxs = sqrt(maxn) + 1;

void dfs(int u) {
    if (visit[u]) return;
    
    topK[u] = {{u, 0}};
    visit[u] = true;
    
    for (int &v : g[u]) {
        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 = -1;
    dist[u] = 0;
    
    vector<int> st = {u};
    
    while (st.size()) {
        u = st.back(); st.pop_back();
        
        if (!invalid[u]) {
            res = max(res, dist[u]);
        }
        
        for (int &v : g[u]) {
            dist[v] = dist[u] + 1;
            st.push_back(v);
        }
    }
    
    return res;
}

struct Query {
    int u; vector<int> a;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    static char buf[1 << 20];
    cout.rdbuf() -> pubsetbuf(buf, sizeof(buf));
    
    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);
    }
    
    vector<Query> queries(q);
    
    for (auto &query : queries) {
        int t, y; cin >> t >> y;
        
        query.u = t;
        query.a.resize(y);
        
        for (int &u : query.a) cin >> u;
    }
    
    {
        int sum = 0;
        
        for (auto &query : queries) {
            sum += query.a.size();
        }
        
        maxs = sqrt(sum) + 1;
    }
    
    for (int i = 1; i <= n; ++i) dfs(i);
    for (auto &u : topK) reverse(begin(u), end(u));
    
    for (auto &query : queries) {
        for (int &u : query.a) {
            invalid[u] = true;
        }
        
        if (query.a.size() < maxs) for (auto &cur : topK[query.u]) {
            if (!invalid[cur.v]) {
                cout << cur.dist << '\n';
                goto skip;
            }
        } else {
            cout << maxDist(query.u) << '\n';
            goto skip;
        }
        
        cout << -1 << '\n';
        skip: true;
        
        for (int &u : query.a) {
            invalid[u] = false;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...