oj.uz

Submission #882398

# Submission time Handle Problem Language Result Execution time Memory
882398 2023-12-03T06:41:47 Z 12345678 Synchronization (JOI13_synchronization) C++17
50 / 100
 164 ms 21624 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];
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(u)-f.find(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])];
            f.add(in[v[x]], -1);
            f.add(out[v[x]]+1, 1);
        }
        else
        {
            dp[findrt(u[x])]+=dp[v[x]]-l[v[x]];
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 19916 KB Output is correct
2 Correct 63 ms 19664 KB Output is correct
3 Correct 69 ms 20996 KB Output is correct
4 Correct 68 ms 21072 KB Output is correct

Subtask #3
10.0 / 10.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 6580 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 13 ms 8280 KB Output is correct
8 Correct 149 ms 21260 KB Output is correct
9 Correct 159 ms 21188 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 21244 KB Output is correct
2 Correct 81 ms 21544 KB Output is correct
3 Correct 81 ms 21528 KB Output is correct
4 Correct 89 ms 21624 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -