제출 #171212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171212		dolphingarlic	동기화 (JOI13_synchronization)	C++14	30 / 100	258 ms	20856 KiB

synchronization

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, q;
bool active[100001];
vector<int> graph[100001];
pair<int, int> edges[200001];

/*
SUBTASK 1
*/

set<int> graph2[100001];
int timer = 0, tin[100001], tout[100001], queries[200001];
int ancestor[100001];

void dfs(int node, int parent) {
    tin[node] = timer++;
    ancestor[node] = node;
    for (int i : graph[node]) {
        if (i != parent) dfs(i, node);
    }
    tout[node] = timer++;
}

bool is_parent(int A, int B) { return tin[A] < tin[B] && tout[A] > tout[B]; }

/*
SUBTASK 2
*/

struct Node {
    int range_l, range_r, info_l, info_r;

    Node operator+(Node b) {
        return {min(range_l, b.range_l), max(range_r, b.range_r),
                min(info_l, b.info_l), max(info_r, b.info_r)};
    }
};

Node segtree[400001], lazy[400001];

void push_lazy(int node, int l, int r) {
    if (!lazy[node].range_l) return;
    if (l == r)
        segtree[node] = lazy[node];
    else
        lazy[node * 2] = lazy[node * 2 + 1] = lazy[node];
    lazy[node] = {0, 0, 0, 0};
}

void build(int node = 1, int l = 1, int r = n) {
    if (l == r)
        segtree[node] = {l, l, l, l};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
    }
}

void update(Node newval, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l > newval.range_r || r < newval.range_l) return;
    if (l >= newval.range_l && r <= newval.range_r)
        lazy[node] = newval;
    else {
        int mid = (l + r) / 2;
        update(newval, node * 2, l, mid);
        update(newval, node * 2 + 1, mid + 1, r);
    }
}

Node query(int pos, int node = 1, int l = 1, int r = n) {
    push_lazy(node, l, r);
    if (l == r) return segtree[node];
    int mid = (l + r) / 2;
    if (pos > mid) return query(pos, node * 2 + 1, mid + 1, r);
    return query(pos, node * 2, l, mid);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        cin >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(edges[i].second);
        graph[edges[i].second].push_back(edges[i].first);
    }

    if (q == 1) {
        FOR(i, 0, m) cin >> queries[i];
        int root;
        cin >> root;
        dfs(root, 0);

        FOR(i, 0, m) {
            int a = edges[queries[i]].first, b = edges[queries[i]].second;
            if (is_parent(a, b)) swap(a, b);

            if (active[queries[i]]) {
                ancestor[a] = a;
            } else {
                for (int j : graph2[a]) graph2[ancestor[b]].insert(j);
                graph2[a].clear();
                graph2[ancestor[b]].insert(a);
                ancestor[a] = ancestor[b];
            }
            active[queries[i]] = !active[queries[i]];
        }

        cout << graph2[root].size() + 1;
    } else {
        build();
        while (m--) {
            int x;
            cin >> x;
            if (active[x]) {
                Node curr = query(x);
                Node l = curr, r = curr;
                l.range_r = x;
                r.range_l = x + 1;
                update(l);
                update(r);
            } else {
                Node newval = query(x) + query(x + 1);
                update(newval);
            }
            active[x] = !active[x];
        }

        while (q--) {
            int x;
            cin >> x;
            Node ans = query(x);
            cout << ans.info_r - ans.info_l + 1 << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40