제출 #519917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519917		Jomnoi	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	4 ms	4940 KiB

bitaro

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 1e5 + 10;
const int INF = 1e9 + 7;

int timer;
vector <int> adj[N], adj2[N];
int degree[N], degree2[N];
int dist[N], sz[N];
int pos[N], st[N];

class SegmentTree {
private :
    int N;
    vector <int> tree;
public :
    SegmentTree(int n) : N(n) {
        tree.resize(4 * N);
        build(1, 1, N);
    }

    void build(int idx, int l, int r) {
        if(l == r) {
            tree[idx] = dist[pos[l]];
            return;
        }

        int mid = (l + r) / 2;
        build(idx * 2, l, mid);
        build(idx * 2 + 1, mid + 1, r);
    }

    void update(int idx, int l, int r, int q, int k) {
        if(l == r) {
            tree[idx] = k;
            return;
        }

        int mid = (l + r) / 2;
        if(q <= mid) {
            update(idx * 2, l, mid, q, k);
        }
        else {
            update(idx * 2 + 1, mid + 1, r, q, k);
        }
        tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
    }

    int query(int idx, int l, int r, int ql, int qr) {
        if(r < ql or qr < l) {
            return -INF;
        }
        if(ql <= l and r <= qr) {
            return tree[idx];
        }

        int mid = (l + r) / 2;
        return max(query(idx * 2, l, mid, ql, qr), query(idx * 2 + 1, mid + 1, r, ql, qr));
    }
};

void dfs(int u) {
    timer++;
    sz[u] = 1;
    st[u] = timer;
    pos[timer] = u;
    for(auto v : adj2[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, Q;
    cin >> n >> m >> Q;
    while(m--) {
        int s, e;
        cin >> s >> e;
        adj[e].push_back(s);
        degree[s]++;
    }

    queue <int> q;
    for(int i = 1; i <= n; i++) {
        if(!degree[i]) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(auto v : adj[u]) {
            if(--degree[v] == 0) {
                adj2[u].push_back(v);
                degree2[v]++;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(!degree2[i]) {
            dfs(i);
        }
    }

    SegmentTree ST(n);
    vector <int> vec;
    while(Q--) {
        int t, y;
        cin >> t >> y;
        vec.clear();
        while(y--) {
            int s;
            cin >> s;
            vec.push_back(s);
        }

        for(auto v : vec) {
            ST.update(1, 1, n, st[v], -INF);
        }
        cout << ST.query(1, 1, n, st[t], st[t] + sz[t] - 1) - dist[t] << '\n';
        for(auto v : vec) {
            ST.update(1, 1, n, st[v], dist[v]);
        }
    }
    return 0;
}

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