oj.uz

Submission #361532

# Submission time Handle Problem Language Result Execution time Memory
361532 2021-01-30T12:39:07 Z RyoPham Synchronization (JOI13_synchronization) C++14
100 / 100
 377 ms 26732 KB 
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2e5 + 5;
const int logn = 18;

int n, m, Q;
pii edges[maxn];
vector<int> gr[maxn];

int ntime = 0;
int tin[maxn], tout[maxn];
int depth[maxn], p[maxn][logn];

int state[maxn];
int total[maxn], lst[maxn];

struct fenwick
{
    int val[maxn];

    void update(int x, int k)
    {
        for(; x < maxn; x += x & -x)
            val[x] += k;
    }

    void update(int l, int r, int k)
    {
        update(l, k);
        update(r + 1, -k);
    }

    int get(int x)
    {
        int res = 0;
        for(; x > 0; x -= x & -x)
            res += val[x];
        return res;
    }
} tree;

void read_input()
{
    cin >> n >> m >> Q;
    for(int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        edges[i] = pii(u, v);
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
}

void dfs(int u, int par)
{
    tin[u] = ++ntime;
    depth[u] = depth[par] + 1;
    p[u][0] = par;
    for(int k = 1; k < logn; ++k)
        p[u][k] = p[p[u][k - 1]][k - 1];
    for(auto&v: gr[u])
        if(v != par) dfs(v, u);
    tout[u] = ntime;
}

int find_root(int u)
{
    for(int k = logn - 1; k >= 0; --k)
        if(tree.get(tin[u]) - tree.get(tin[p[u][k]]) == depth[u] - depth[p[u][k]])
            u = p[u][k];
    return u;
}

void solve()
{
    dfs(1, 0);
    fill(total + 1, total + n + 1, 1);
    fill(lst + 1, lst + n + 1, 0);
    for(; m > 0; --m)
    {
        int id;
        cin >> id;
        int u = edges[id].fi, v = edges[id].se;
        if(depth[u] > depth[v]) swap(u, v);
        if(state[id])
        {
            total[v] = lst[v] = total[find_root(v)];
            tree.update(tin[v], tout[v], -1);
        }
        else
        {
            total[find_root(u)] += total[v] - lst[v];
            tree.update(tin[v], tout[v], 1);
        }
        state[id] ^= 1;
    }
    for(; Q > 0; --Q)
    {
        int u;
        cin >> u;
        cout << total[find_root(u)] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 3 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 3 ms 5100 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 18 ms 6636 KB Output is correct
8 Correct 18 ms 6656 KB Output is correct
9 Correct 18 ms 6636 KB Output is correct
10 Correct 253 ms 21320 KB Output is correct
11 Correct 275 ms 21356 KB Output is correct
12 Correct 290 ms 25836 KB Output is correct
13 Correct 146 ms 21092 KB Output is correct
14 Correct 178 ms 20716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 23404 KB Output is correct
2 Correct 113 ms 23404 KB Output is correct
3 Correct 123 ms 25212 KB Output is correct
4 Correct 125 ms 25324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5356 KB Output is correct
7 Correct 28 ms 7276 KB Output is correct
8 Correct 377 ms 26604 KB Output is correct
9 Correct 349 ms 26604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 26732 KB Output is correct
2 Correct 203 ms 26348 KB Output is correct
3 Correct 201 ms 26476 KB Output is correct
4 Correct 196 ms 26348 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 6 ms 5376 KB Output is correct
6 Correct 25 ms 6764 KB Output is correct
7 Correct 310 ms 22124 KB Output is correct
8 Correct 356 ms 26604 KB Output is correct
9 Correct 178 ms 22244 KB Output is correct
10 Correct 218 ms 21996 KB Output is correct
11 Correct 159 ms 24556 KB Output is correct
12 Correct 165 ms 24612 KB Output is correct
13 Correct 196 ms 26476 KB Output is correct