oj.uz

Submission #623599

# Submission time Handle Problem Language Result Execution time Memory
623599 2022-08-06T04:10:29 Z Hanksburger Synchronization (JOI13_synchronization) C++17
100 / 100
 245 ms 23368 KB 
#include <bits/stdc++.h>
using namespace std;
int par[100005][17], bit[100005], ok[100005], in[100005], out[100005], a[100005], b[100005], n, m, q, t;
vector<pair<int, int> > edge;
vector<int> adj[100005];
void update(int x, int y)
{
    for (int i=x; i<=n; i+=i&(-i))
        bit[i]+=y;
}
int query(int x)
{
    int ans=0;
    for (int i=x; i; i-=i&(-i))
        ans+=bit[i];
    return ans;
}
int findPar(int u)
{
    for (int i=16; i>=0; i--)
        if (query(in[u])==query(in[par[u][i]]))
            u=par[u][i];
    return u;
}
void dfs(int u, int p)
{
    par[u][0]=p;
    for (int i=1; i<=16; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    in[u]=++t;
    for (int v:adj[u])
        if (v!=p)
            dfs(v, u);
    out[u]=t+1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        edge.push_back({u, v});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    for (int i=1; i<=n; i++)
    {
        update(in[i], 1);
        update(out[i], -1);
        a[i]=1;
    }
    for (int i=1; i<=m; i++)
    {
        int x, u, v, w;
        cin >> x;
//        cout << "i=" << i << '\n';
        u=edge[x-1].first;
        v=edge[x-1].second;
        if (par[u][0]==v)
            swap(u, v);
        w=findPar(u);
        if (ok[x])
        {
            a[v]=b[v]=a[w];
            update(in[v], 1);
            update(out[v], -1);
        }
        else
        {
            a[w]+=a[v]-b[v];
            update(in[v], -1);
            update(out[v], 1);
        }
        ok[x]^=1;
//        cout << "------------- a: ";
//        for (int j=1; j<=n; j++)
//            cout << a[j] << ' ';
//        cout << '\n';
//        cout << "------------- bit: ";
//        for (int j=1; j<=n; j++)
//            cout << bit[j] << ' ';
//        cout << '\n';
//        cout << "------------- bit: ";
//        for (int j=1; j<=n; j++)
//            cout << query(j) << ' ';
//        cout << '\n';
    }
    for (int i=1; i<=q; i++)
    {
        int x;
        cin >> x;
        cout << a[findPar(x)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 13 ms 4148 KB Output is correct
8 Correct 13 ms 4224 KB Output is correct
9 Correct 12 ms 4180 KB Output is correct
10 Correct 172 ms 17936 KB Output is correct
11 Correct 174 ms 17980 KB Output is correct
12 Correct 188 ms 22568 KB Output is correct
13 Correct 90 ms 17888 KB Output is correct
14 Correct 117 ms 16908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 18556 KB Output is correct
2 Correct 81 ms 19580 KB Output is correct
3 Correct 89 ms 21556 KB Output is correct
4 Correct 85 ms 21596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 18 ms 4720 KB Output is correct
8 Correct 232 ms 23344 KB Output is correct
9 Correct 226 ms 23368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 21944 KB Output is correct
2 Correct 137 ms 22688 KB Output is correct
3 Correct 142 ms 22836 KB Output is correct
4 Correct 137 ms 22816 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 3 ms 2772 KB Output is correct
6 Correct 17 ms 4308 KB Output is correct
7 Correct 239 ms 18856 KB Output is correct
8 Correct 245 ms 23340 KB Output is correct
9 Correct 118 ms 19000 KB Output is correct
10 Correct 140 ms 18208 KB Output is correct
11 Correct 110 ms 20984 KB Output is correct
12 Correct 106 ms 20976 KB Output is correct
13 Correct 135 ms 22860 KB Output is correct