oj.uz

Submission #577945

# Submission time Handle Problem Language Result Execution time Memory
577945 2022-06-15T14:11:20 Z Huy Synchronization (JOI13_synchronization) C++17
100 / 100
 560 ms 27796 KB 
#include<bits/stdc++.h>
//#define int long long
#define pii pair<ll,ll>
#define fi first
#define se second

using namespace std;
using ll = long long;
using ldb = long double;
const int N = (int)5e5+2;
const int maxN = (int)2e5 + 5;
const int mod = 1e9 + 7;
const ll infty = 1e18;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,m,q;
vector<vector<int>> adj;
int anc[25][maxN];
int lg[maxN];
int depth[maxN];
int TimeDFS = 0;
int sta[maxN];
int fin[maxN];
int now[maxN];
int lst[maxN];
int x[maxN],y[maxN];
int apr[maxN];

void Prepare()
{
    lg[1] = 0;
    for(int i = 2;i < maxN;i++)
    {
        lg[i] = lg[i/2] + 1;
    }
}

void Read()
{
    cin >> n >> m >> q;
    adj.resize(n+1);
    for(int i = 1;i < n;i++)
    {
        int u,v;
        cin >> u >> v;
        x[i] = u;
        y[i] = v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int bit[maxN];

void Update(int idx,int val)
{
    while(idx <= n)
    {
        bit[idx] += val;
        idx += (idx & (-idx));
    }
}

void UpdRange(int l,int r,int val)
{
    Update(l,val);
    Update(r+1,-val);
}

int Get(int idx)
{
    if(idx == 0) return -1;
    int res = 0;
    while(idx > 0)
    {
        res += bit[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

void preDFS(int u,int p)
{
    sta[u] = ++TimeDFS;
    UpdRange(sta[u],sta[u],depth[u]+1);
    now[u] = 1;
    lst[u] = 0;
    for(int v : adj[u])
    {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        anc[0][v] = u;
        for(int i = 1;i <= lg[n];i++)
        {
            anc[i][v] = anc[i-1][anc[i-1][v]];
        }
        preDFS(v,u);
    }
    fin[u] = TimeDFS;
}

int Find(int u)
{
    int comp = Get(sta[u]);
    for(int i = lg[n];i >= 0;i--)
    {
        if(Get(sta[anc[i][u]]) == Get(sta[u])) u = anc[i][u];
    }
    return u;
}

void Solve()
{
    Prepare();
    preDFS(1,0);
    for(int i = 1;i <= m;i++)
    {
        int edg_id;
        cin >> edg_id;
        if(depth[x[edg_id]] > depth[y[edg_id]])
        {
            swap(x[edg_id],y[edg_id]);
        }
        apr[edg_id]++;
        if(apr[edg_id]%2)
        {
            UpdRange(sta[y[edg_id]],fin[y[edg_id]],-1);
            int par = Find(y[edg_id]);
            now[par] += now[y[edg_id]] - lst[y[edg_id]];
            now[y[edg_id]] = lst[y[edg_id]] = now[par];
        }
        else
        {
            int par = Find(y[edg_id]);
            //now[par] += now[y[edg_id]] - lst[y[edg_id]];
            now[y[edg_id]] = lst[y[edg_id]] = now[par];
            UpdRange(sta[y[edg_id]],fin[y[edg_id]],1);
        }
    }
    //cout << sta[2] <<' '<< fin[2];return;
    //cout << Get(sta[3]);return;
    while(q--)
    {
        int u;
        cin >> u;
        int par = Find(u);
        cout << now[par] <<'\n';
    }
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

/*
13 1
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
*/

Compilation message

synchronization.cpp: In function 'int Find(int)':
synchronization.cpp:116:9: warning: unused variable 'comp' [-Wunused-variable]
  116 |     int comp = Get(sta[u]);
      |         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 15 ms 2900 KB Output is correct
8 Correct 15 ms 2772 KB Output is correct
9 Correct 15 ms 2784 KB Output is correct
10 Correct 403 ms 19276 KB Output is correct
11 Correct 409 ms 19216 KB Output is correct
12 Correct 439 ms 26996 KB Output is correct
13 Correct 291 ms 19268 KB Output is correct
14 Correct 227 ms 18608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 20924 KB Output is correct
2 Correct 109 ms 22728 KB Output is correct
3 Correct 104 ms 26316 KB Output is correct
4 Correct 102 ms 26408 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1092 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 24 ms 3704 KB Output is correct
8 Correct 457 ms 27796 KB Output is correct
9 Correct 560 ms 27760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 24824 KB Output is correct
2 Correct 161 ms 27368 KB Output is correct
3 Correct 169 ms 27504 KB Output is correct
4 Correct 164 ms 27504 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 4 ms 1384 KB Output is correct
6 Correct 23 ms 2900 KB Output is correct
7 Correct 475 ms 20076 KB Output is correct
8 Correct 481 ms 27760 KB Output is correct
9 Correct 358 ms 20212 KB Output is correct
10 Correct 360 ms 19896 KB Output is correct
11 Correct 128 ms 24144 KB Output is correct
12 Correct 164 ms 24116 KB Output is correct
13 Correct 168 ms 27608 KB Output is correct