oj.uz

Submission #136987

# Submission time Handle Problem Language Result Execution time Memory
136987 2019-07-26T20:06:23 Z egorlifar Synchronization (JOI13_synchronization) C++17
100 / 100
 288 ms 17532 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
const int MAXN = 100228;


int n, m, q;
vector<pair<int, int> > g[MAXN];
int pr[MAXN];
int timer = 0;
int downe[MAXN];
int who[MAXN];
int dp[MAXN];
int ob[MAXN];
bool used[MAXN];
int in[MAXN], out[MAXN];


void dfs(int u, int p) {
    pr[u] = p;
    timer++;
    in[u] = timer;
    who[timer] = u;
    for (auto h: g[u]) {
        if (h.first == p) {
            continue;
        }
        downe[h.second] = h.first;
        dfs(h.first, u);
    }
    out[u] = timer;
}



int d[MAXN * 4];


void update(int v, int l, int r, int pos, int x) {
    if (l == r) {
        d[v] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        update(v * 2, l, mid, pos, x);
    } else {
        update(v * 2 + 1, mid + 1, r, pos, x);
    }
    d[v] = max(d[v * 2], d[v * 2 + 1]);
}
 

int get(int v, int l, int r, int tl, int tr, int x) {
    if (l > r || tl > r || l > tr || tl > tr || d[v] < x) {
        return -1;
    }
    if (l == r) {
        return who[l];
    }
    int mid = (l + r) >> 1;
    int pos = -1;
    if (d[v * 2 + 1] >= x) {
        pos = get(v * 2 + 1, mid + 1, r, tl, tr, x);
    }
    if (pos == -1 && d[v * 2] >= x) {
        pos = get(v * 2, l, mid, tl, tr, x);
    }
    return pos;
}


int getRoot(int v) {
    int cur = get(1, 1, n, 1, in[v], out[v]);
    if (cur != -1) {
        return cur;
    }
    return 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        update(1, 1, n, in[i], out[i]);
    }
    for (int i = 1; i <= m; i++) {
        int id;
        cin >> id;
        int y = downe[id];
        int x = pr[y];
        if (!used[id]){
            int root = getRoot(x);
            dp[root] += dp[y] - ob[y];
            update(1, 1, n, in[y], 0);
        } else {
            int root = getRoot(x);
            dp[y] = dp[root];
            ob[y] = dp[root];
            update(1, 1, n, in[y], out[y]);
        }
        used[id] ^= 1;
    }
    for (int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        cout << dp[getRoot(x)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2808 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 19 ms 3676 KB Output is correct
8 Correct 20 ms 3704 KB Output is correct
9 Correct 20 ms 3704 KB Output is correct
10 Correct 233 ms 12536 KB Output is correct
11 Correct 239 ms 12568 KB Output is correct
12 Correct 205 ms 16840 KB Output is correct
13 Correct 135 ms 12392 KB Output is correct
14 Correct 151 ms 11640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 14196 KB Output is correct
2 Correct 107 ms 14024 KB Output is correct
3 Correct 103 ms 15736 KB Output is correct
4 Correct 103 ms 15736 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2684 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 21 ms 4216 KB Output is correct
8 Correct 241 ms 17512 KB Output is correct
9 Correct 235 ms 17528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 17528 KB Output is correct
2 Correct 135 ms 16924 KB Output is correct
3 Correct 131 ms 17016 KB Output is correct
4 Correct 131 ms 17016 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 6 ms 2940 KB Output is correct
6 Correct 23 ms 3800 KB Output is correct
7 Correct 288 ms 13408 KB Output is correct
8 Correct 235 ms 17532 KB Output is correct
9 Correct 196 ms 13548 KB Output is correct
10 Correct 240 ms 12920 KB Output is correct
11 Correct 149 ms 15348 KB Output is correct
12 Correct 136 ms 15348 KB Output is correct
13 Correct 132 ms 16896 KB Output is correct