oj.uz

Submission #240663

# Submission time Handle Problem Language Result Execution time Memory
240663 2020-06-20T14:30:40 Z AM1648 Synchronization (JOI13_synchronization) C++17
100 / 100
 897 ms 24344 KB 
/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 100010;
const ll maxnlg = 20;

ll n, m, Q;
vpii g[maxn];
ll ver[maxn], st[maxn], ft[maxn], pars[maxnlg][maxn];
ll fen[maxn];
ll info[maxn], hist[maxn], state[maxn];

ll tim = 0;
void dfs_init(ll x, ll par) {
    st[x] = tim++;
    pars[0][x] = par;
    fori (i, maxnlg - 1) pars[i + 1][x] = pars[i][pars[i][x]];
    for (auto [y, e] : g[x]) if (y != par) {
        ver[e] = y;
        dfs_init(y, x);
    }
    ft[x] = tim;
}

void update(ll i, ll v) {
    for (++i; i < maxn; i += i & -i) fen[i] += v;
}

ll get(ll i) {
    ll s = 0;
    for (++i; i; i ^= i & -i) s += fen[i];
    return s;
}

ll find_root(ll x) {
    ll v = get(st[x]);
    forir (i, maxnlg) {
        if (get(st[pars[i][x]]) == v) x = pars[i][x];
    }
    return x;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> m >> Q;
    fori (i, n - 1) {
        ll a, b; cin >> a >> b; --a, --b;
        g[a].eb(b, i), g[b].eb(a, i);
    }
    dfs_init(0, 0);
    fill(info, info + n, 1);
    // state = 1 -> open
    fori (i, n) update(st[i], 1), update(ft[i], -1);
    fori (i, m) {
        ll e; cin >> e; --e;
        ll x = ver[e];
        ll rt = find_root(pars[0][x]);
        if (state[e]) {
            hist[x] = info[x] = info[rt];
            update(st[x], 1), update(ft[x], -1);
        } else {
            info[rt] += info[x] - hist[x];
            update(st[x], -1), update(ft[x], 1);
        }
        state[e] ^= 1;
    }
    fori (i, Q) {
        ll x; cin >> x; --x;
        ll rt = find_root(x);
        cout << info[rt] << '\n';
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 7 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 8 ms 2944 KB Output is correct
7 Correct 26 ms 4480 KB Output is correct
8 Correct 24 ms 4480 KB Output is correct
9 Correct 24 ms 4480 KB Output is correct
10 Correct 551 ms 19448 KB Output is correct
11 Correct 534 ms 19576 KB Output is correct
12 Correct 561 ms 23548 KB Output is correct
13 Correct 129 ms 19052 KB Output is correct
14 Correct 312 ms 18424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 20836 KB Output is correct
2 Correct 128 ms 20724 KB Output is correct
3 Correct 133 ms 22648 KB Output is correct
4 Correct 130 ms 22520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2828 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 8 ms 3072 KB Output is correct
7 Correct 31 ms 4988 KB Output is correct
8 Correct 816 ms 24344 KB Output is correct
9 Correct 897 ms 24316 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 24312 KB Output is correct
2 Correct 202 ms 23544 KB Output is correct
3 Correct 198 ms 23672 KB Output is correct
4 Correct 199 ms 23672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 8 ms 2944 KB Output is correct
6 Correct 30 ms 4600 KB Output is correct
7 Correct 684 ms 20220 KB Output is correct
8 Correct 685 ms 24208 KB Output is correct
9 Correct 172 ms 20200 KB Output is correct
10 Correct 392 ms 19704 KB Output is correct
11 Correct 161 ms 22004 KB Output is correct
12 Correct 179 ms 22132 KB Output is correct
13 Correct 205 ms 23752 KB Output is correct