oj.uz

Submission #689974

# Submission time Handle Problem Language Result Execution time Memory
689974 2023-01-30T00:03:48 Z vjudge1 Synchronization (JOI13_synchronization) C++17
100 / 100
 608 ms 36036 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second
ii e[maxn];
int n,m,q;
vector <int> adj[maxn];
int d[maxn],c[maxn];
int par[19][maxn];
int in[maxn],out[maxn],cnt;
int f[maxn];
bool dau[maxn];

void update(int x, int val)
{
    while (x<=n)
    {
        f[x]+=val;
        x+=(x&-x);
    }
}

int get(int x)
{
    int temp=0;
    while (x>0)
    {
        temp+=f[x];
        x-=(x&-x);
    }
    return temp;
}

void updaterange(int l, int r, int val)
{
    update(l,val); update(r+1,-val);
}

void dfs(int x, int p)
{
    in[x]=++cnt;
    par[0][x] = p;
    for (int i=1; i<=18; i++) par[i][x]=par[i-1][par[i-1][x]];
    for (int i:adj[x])
        if (i!=p) dfs(i,x);
    out[x]=cnt;
}

int get_root(int x)
{
    int u=x; int val=get(in[u]);
    for (int i=18; i>=0; i--)
        if (get(in[par[i][u]])==get(in[x])) u=par[i][u];
    return u;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++)
    {
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        e[i]={u,v};
    }
    fill_n(d,n+1,1);
    fill_n(dau,n+1,0);
    dfs(1,1);
    for (int i=1; i<=n; i++) updaterange(in[i],out[i],1);
    for (int i=1; i<=m; i++)
    {
        int id; cin>>id;
        int u=e[id].ff; int v=e[id].ss;
        if (v==par[0][u]) swap(u,v);
//        cout<<u<<" -> "<<v<<'\n';
        if (!dau[id])
        {
            d[get_root(u)]+=d[v]-c[v];
        }
        else
        {
            d[v]=c[v]=d[get_root(u)];
        }
//        cout<<i<<": ";
//        for (int j=1; j<=n; j++) cout<<d[j]<<' '; cout<<'\n';
        if (!dau[id]) updaterange(in[v],out[v],-1);
        else updaterange(in[v],out[v],1);
        dau[id]^=1;
    }
    for (int i=1; i<=q; i++)
    {
        int u; cin>>u;
        u=get_root(u);
        cout<<d[u]<<'\n';
    }
}

Compilation message

synchronization.cpp: In function 'long long int get_root(long long int)':
synchronization.cpp:54:18: warning: unused variable 'val' [-Wunused-variable]
   54 |     int u=x; int val=get(in[u]);
      |                  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5160 KB Output is correct
4 Correct 3 ms 5160 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 4 ms 5428 KB Output is correct
7 Correct 19 ms 7764 KB Output is correct
8 Correct 24 ms 7772 KB Output is correct
9 Correct 18 ms 7764 KB Output is correct
10 Correct 494 ms 31512 KB Output is correct
11 Correct 506 ms 31532 KB Output is correct
12 Correct 537 ms 35716 KB Output is correct
13 Correct 88 ms 31352 KB Output is correct
14 Correct 271 ms 30160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 32780 KB Output is correct
2 Correct 89 ms 32456 KB Output is correct
3 Correct 107 ms 34488 KB Output is correct
4 Correct 109 ms 34400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5164 KB Output is correct
2 Correct 3 ms 5164 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 24 ms 8272 KB Output is correct
8 Correct 584 ms 35788 KB Output is correct
9 Correct 608 ms 35804 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 36036 KB Output is correct
2 Correct 185 ms 35380 KB Output is correct
3 Correct 167 ms 35564 KB Output is correct
4 Correct 174 ms 35660 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 24 ms 7860 KB Output is correct
7 Correct 563 ms 31704 KB Output is correct
8 Correct 587 ms 35748 KB Output is correct
9 Correct 124 ms 32228 KB Output is correct
10 Correct 317 ms 31308 KB Output is correct
11 Correct 121 ms 34020 KB Output is correct
12 Correct 120 ms 34004 KB Output is correct
13 Correct 162 ms 35556 KB Output is correct