Submission #361532

#	Time	Username	Problem	Language	Result	Execution time	Memory
361532		RyoPham	Synchronization (JOI13_synchronization)	C++14	100 / 100	377 ms	26732 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40