Submission #1244562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244562		tvgk	Synchronization (JOI13_synchronization)	C++20	100 / 100	216 ms	29612 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int in[mxN], out[mxN], num, n, m, q, u[mxN], v[mxN], bit[mxN], par[mxN][30], mem[mxN], ans[mxN];
vector<int> w[mxN];

void Upd(int j, int val)
{
    while (j <= n)
    {
        bit[j] += val;
        j += j & (-j);
    }
}

int Get(int j)
{
    int res = 0;
    while (j > 0)
    {
        res += bit[j];
        j -= j & (-j);
    }
    return res;
}

void DFS(int j)
{
    in[j] = ++num;

    for (int i = 1; i <= 20; i++)
        par[j][i] = par[par[j][i - 1]][i - 1];

    for (int i : w[j])
    {
        if (in[i])
            continue;

        par[i][0] = j;
        DFS(i);
    }
    out[j] = num + 1;

    Upd(in[j], 1);
    Upd(out[j], -1);
}

int Find(int j)
{
    int tmp = Get(in[j]);
    for (int i = 20; i >= 0; i--)
    {
        if (Get(in[par[j][i]]) == tmp)
            j = par[j][i];
    }
    return j;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        cin >> u[i] >> v[i];
        w[u[i]].push_back(v[i]);
        w[v[i]].push_back(u[i]);
    }
    DFS(1);

    for (int i = 1; i <= n; i++)
        ans[i] = 1;

    for (int i = 1; i < n; i++)
    {
        if (par[u[i]][0] == v[i])
            swap(u[i], v[i]);
    }

    for (int i = 1; i <= m; i++)
    {
        int id;
        cin >> id;

        int root = Find(u[id]);
        if (mem[id] == -1)
        {
            Upd(in[v[id]], 1);
            Upd(out[v[id]], -1);

            mem[id] = ans[v[id]] = ans[root];
        }
        else
        {
            Upd(in[v[id]], -1);
            Upd(out[v[id]], 1);

            ans[v[id]] = ans[root] = ans[v[id]] + ans[root] - mem[id];
            mem[id] = -1;
        }
    }

    for (int i = 1; i <= q; i++)
    {
        int tmp;
        cin >> tmp;
        cout << ans[Find(tmp)] << '\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40