Submission #473999

#	Time	Username	Problem	Language	Result	Execution time	Memory
473999		Lam_lai_cuoc_doi	Synchronization (JOI13_synchronization)	C++17	100 / 100	312 ms	29364 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
constexpr int Inf = 1e9 + 7;

struct FenwickTree
{
    int n;
    int a[N];
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    void Update(int l, int r, int v)
    {
        Update(l, v);
        Update(r + 1, -v);
    }
    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }
} f;

vector<int> adj[N];
int n, m, q, l, in[N], out[N], par[N][17];
int ans[N], synced[N], u[N], v[N], ranks[N];
bool ck[N];

void Read()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].emplace_back(v[i]);
        adj[v[i]].emplace_back(u[i]);
    }
}

void dfs(int v, int p = 0)
{
    in[v] = out[v] = ++l;

    for (int i = 1; i < 17; ++i)
        par[v][i] = par[par[v][i - 1]][i - 1];

    synced[v] = 0;
    ans[v] = 1;

    for (auto i : adj[v])
        if (i != p)
        {
            ranks[i] = ranks[v] + 1;
            par[i][0] = v;
            dfs(i, v);
            out[v] = out[i];
        }
}

int GetPar(int v)
{
    int tmp = f.Get(in[v]), tmp2;

    for (int i = 16; ~i; --i)
        if (ranks[par[v][i]] != 0 && (tmp2 = f.Get(in[par[v][i]])) == tmp - (1 << i))
        {
            v = par[v][i];
            tmp = tmp2;
        }

    return v;
}

void Solve()
{
    ranks[1] = 1;
    dfs(1);
    f.n = n;

    while (m--)
    {
        int x;
        cin >> x;
        if (ranks[u[x]] < ranks[v[x]])
            swap(u[x], v[x]);

        ck[x] = !ck[x];

        if (ck[x])
        {
            int z = GetPar(v[x]);
            ans[z] = ans[z] + ans[u[x]] - synced[u[x]];
            synced[u[x]] = ans[z];

            f.Update(in[u[x]], out[u[x]], 1);
        }
        else
        {
            int z = GetPar(u[x]);
            synced[u[x]] = ans[u[x]] = ans[z];
            f.Update(in[u[x]], out[u[x]], -1);
        }
    }

    while (q--)
    {
        int x;
        cin >> x;
        cout << ans[GetPar(x)] << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

synchronization.cpp: In function 'void read(T&)':
synchronization.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

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