oj.uz

Submission #171215

# Submission time Handle Problem Language Result Execution time Memory
171215 2019-12-27T19:14:57 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
30 / 100
 252 ms 27768 KB 
#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;
    graph2[node].insert(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[ancestor[a]]) graph2[ancestor[b]].insert(j);
                ancestor[ancestor[a]] = ancestor[b];
            }
            active[queries[i]] = !active[queries[i]];
        }

        cout << graph2[root].size();
    } 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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 2 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Incorrect 8 ms 7416 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 27768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 9 ms 7544 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 27 ms 8696 KB Output is correct
8 Correct 252 ms 18652 KB Output is correct
9 Correct 251 ms 18680 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 18760 KB Output is correct
2 Correct 152 ms 19192 KB Output is correct
3 Correct 144 ms 19320 KB Output is correct
4 Correct 146 ms 19264 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -