oj.uz

Submission #473999

# Submission time Handle Problem Language Result Execution time Memory
473999 2021-09-16T15:19:52 Z Lam_lai_cuoc_doi Synchronization (JOI13_synchronization) C++17
100 / 100
 312 ms 29364 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5800 KB Output is correct
5 Correct 4 ms 5836 KB Output is correct
6 Correct 4 ms 5964 KB Output is correct
7 Correct 15 ms 7244 KB Output is correct
8 Correct 17 ms 7296 KB Output is correct
9 Correct 15 ms 7244 KB Output is correct
10 Correct 195 ms 20932 KB Output is correct
11 Correct 223 ms 20772 KB Output is correct
12 Correct 252 ms 28552 KB Output is correct
13 Correct 105 ms 20648 KB Output is correct
14 Correct 143 ms 20228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22500 KB Output is correct
2 Correct 96 ms 24260 KB Output is correct
3 Correct 111 ms 27900 KB Output is correct
4 Correct 111 ms 27888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 4 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5804 KB Output is correct
5 Correct 3 ms 5848 KB Output is correct
6 Correct 5 ms 6068 KB Output is correct
7 Correct 22 ms 8136 KB Output is correct
8 Correct 305 ms 29364 KB Output is correct
9 Correct 312 ms 29324 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 26388 KB Output is correct
2 Correct 173 ms 28948 KB Output is correct
3 Correct 170 ms 29112 KB Output is correct
4 Correct 191 ms 29124 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5800 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5944 KB Output is correct
6 Correct 18 ms 7372 KB Output is correct
7 Correct 289 ms 21608 KB Output is correct
8 Correct 302 ms 29312 KB Output is correct
9 Correct 127 ms 21888 KB Output is correct
10 Correct 181 ms 21548 KB Output is correct
11 Correct 130 ms 25744 KB Output is correct
12 Correct 128 ms 25660 KB Output is correct
13 Correct 178 ms 29084 KB Output is correct