Submission #366465

#	Time	Username	Problem	Language	Result	Execution time	Memory
366465		idk321	Synchronization (JOI13_synchronization)	C++11	100 / 100	451 ms	25080 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
vector<int> adj[N];
array<int, 2> edge[N];
int timer = 0;
int tin[N];
int tout[N];
int anc[N][20];
int info[N];
int bit[N];

void addNum(int pos, int num)
{
    for (int i = pos; i < N; i = i | (i + 1)) bit[i] += num;
}

int getSum(int pos)
{
    int sum = 0;
    for (int i = pos; i >= 0; i = (i &(i + 1)) - 1 ) sum += bit[i];

    return sum;
}

void dfs(int node, int par)
{
    tin[node] = timer;
    timer++;
    anc[node][0] = par;
    for (int i = 1; i < 20; i++)
    {
        if (anc[node][i - 1] == -1)
        {
            anc[node][i] = -1;
        } else
        {
            anc[node][i] = anc[anc[node][i - 1]][i - 1];
        }
    }

    for (int next : adj[node])
    {
        if (next == par) continue;
        dfs(next, node);
    }
    tout[node] = timer;
}

int getRoot(int node)
{
    for (int i = 19; i >= 0; i--)
    {
        if (anc[node][i] != -1 && getSum(tin[anc[node][i]]) == getSum(tin[node])) node = anc[node][i];
    }
    return node;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        edge[i] = {x, y};
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, -1);
    vector<int> change(m);
    for (int i = 0; i < m; i++) cin >> change[i];
    bool exist[N] = {};
    int passed[N] = {};


    for (int i = 1; i <= n; i++)
    {
        info[i] = 1;
        addNum(tin[i], 1);
        addNum(tout[i], -1);
    }


    for (int i = 0; i < m; i++)
    {
        int e = change[i];
        int a = edge[e][0];
        int b = edge[e][1];
        if (anc[a][0] == b) swap(a, b);
        if (exist[e])
        {
            a = getRoot(a);
            info[b] = info[a];
            passed[e] = info[a];
            addNum(tin[b], 1);
            addNum(tout[b], -1);
        } else
        {
            a = getRoot(a);
            b = getRoot(b);
            info[a] = info[b] + info[a] - passed[e];
            info[b] = 0;
            passed[e] = info[b] + info[a] - passed[e];
            addNum(tin[b], -1);
            addNum(tout[b], 1);
        }

        exist[e] = !exist[e];
    }

    for (int q1 = 0; q1 < q; q1++)
    {

        int c;
        cin >> c;
        c = getRoot(c);
        cout << info[c] << "\n";
    }

}

/*
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/

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