oj.uz

Submission #882403

# Submission time Handle Problem Language Result Execution time Memory
882403 2023-12-03T07:03:05 Z 12345678 Synchronization (JOI13_synchronization) C++17
100 / 100
 188 ms 24232 KB 
#include <bits/stdc++.h>
 
using namespace std;

const int nx=1e5+5, kx=17;
int n, m, q, u[nx], v[nx], pa[nx][kx], lvl[nx], on[nx], dp[nx], l[nx], in[nx], out[nx], t, x, vs[nx], rt;
vector<pair<int, int>> d[nx];
 
void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1; pa[u][0]=p; dp[u]=1; in[u]=++t;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto [v, idx]:d[u]) if (v!=p) dfs(v, u);
    out[u]=t;
}

struct fenwick
{
    int d[nx];
    void add(int idx, int vl)
    {
        for (int i=idx; i<nx; i+=(i&-i)) d[i]+=vl;
    }
    int find(int idx)
    {
        int res=0;
        for (int i=idx; i>0; i-=(i&-i)) res+=d[i];
        return res;
    }
} f;

int findrt(int u)
{
    for (int i=kx-1; i>=0; i--) if (f.find(in[u])-f.find(in[pa[u][i]])==lvl[u]-lvl[pa[u][i]]) u=pa[u][i];
    return u;
}

void dfs2(int u, int vl)
{
    vs[u]=1;
    dp[u]=vl;
    for (auto [v, idx]:d[u]) if (on[idx]&&v!=pa[u][0]) dfs2(v, vl); 
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++) cin>>u[i]>>v[i], d[u[i]].push_back({v[i], i}), d[v[i]].push_back({u[i], i});
    dfs(1, 1);
    for (int i=1; i<=m; i++)
    {
        cin>>x;
        if (lvl[u[x]]>lvl[v[x]]) swap(u[x], v[x]);
        if (on[x])
        {
            l[v[x]]=dp[v[x]]=dp[findrt(v[x])];
            //cout<<"here "<<findrt(v[x])<<' '<<dp[v[x]]<<'\n';
            f.add(in[v[x]], -1);
            f.add(out[v[x]]+1, 1);
        }
        else
        {
            dp[findrt(u[x])]+=dp[v[x]]-l[v[x]];
            //cout<<"here2 "<<findrt(u[x])<<' '<<dp[findrt(u[x])]<<'\n';
            f.add(in[v[x]], 1);
            f.add(out[v[x]]+1, -1);
        }
        on[x]=!on[x];
    }
    for (int i=1; i<=n; i++) if (!vs[i]) dfs2(findrt(i), dp[findrt(i)]);
    while (q--) cin>>x, cout<<dp[x]<<'\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6624 KB Output is correct
7 Correct 13 ms 8084 KB Output is correct
8 Correct 13 ms 8028 KB Output is correct
9 Correct 13 ms 8028 KB Output is correct
10 Correct 153 ms 19396 KB Output is correct
11 Correct 154 ms 19284 KB Output is correct
12 Correct 163 ms 23380 KB Output is correct
13 Correct 89 ms 19188 KB Output is correct
14 Correct 87 ms 18588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19964 KB Output is correct
2 Correct 68 ms 19816 KB Output is correct
3 Correct 76 ms 21152 KB Output is correct
4 Correct 75 ms 20984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 14 ms 8284 KB Output is correct
8 Correct 174 ms 21248 KB Output is correct
9 Correct 188 ms 21188 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 21288 KB Output is correct
2 Correct 85 ms 21584 KB Output is correct
3 Correct 86 ms 21740 KB Output is correct
4 Correct 85 ms 21668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 14 ms 8132 KB Output is correct
7 Correct 160 ms 20024 KB Output is correct
8 Correct 186 ms 24232 KB Output is correct
9 Correct 96 ms 20132 KB Output is correct
10 Correct 110 ms 20272 KB Output is correct
11 Correct 81 ms 23088 KB Output is correct
12 Correct 80 ms 22996 KB Output is correct
13 Correct 87 ms 23828 KB Output is correct