oj.uz

Submission #1103148

# Submission time Handle Problem Language Result Execution time Memory
1103148 2024-10-20T09:26:32 Z khoile25108 Synchronization (JOI13_synchronization) C++14
100 / 100
 440 ms 22732 KB 
#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 105;

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};

int n, m, q, times;
vector<int> g[N];
int is_on[N], seg[4*N], par[N], head[N], sze[N], h[N], old[N], cur[N], pos[N], node[N];
ii canh[N];

void up(int id, int l, int r, int pos)
{
    if(pos < l || pos > r)
        return;
    if(l == r)
    {
        seg[id] ^= 1;
        return;
    }
    int mid = l + r >> 1;
    up(id << 1, l, mid, pos);
    up(id << 1 | 1, mid + 1, r, pos);
    seg[id] = seg[id << 1] + seg[id << 1 | 1];
}

int get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u)
        return 0;
    if(l >= u && r <= v)
        return seg[id];
    int mid = l + r >> 1;
    return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}

void dfs(int u, int p)
{
    par[u] = p;
    for(int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if(v == p)
            continue;
        h[v] = h[u] + 1;
        dfs(v,u);
        sze[u] += sze[v];
        if(g[u][0] == p || sze[g[u][0]] < sze[v])
            swap(g[u][i], g[u][0]);
    }
}

void hld(int u, int p)
{
    pos[u] = ++times;
    node[times] = u;
    head[u] = (g[p][0] == u ? head[p] : u);
    for(int v : g[u])
    {
        if(v == p)
            continue;
        hld(v,u);
    }
}

int get_root(int u)
{
    while(par[u] )
    {
        if(!get(1,1,n,pos[u],pos[u]))
            return u;
        int v = head[u];
        int l = pos[v] + 1;
        int r = pos[u];
        if(l <= r)
        {
            if(get(1,1,n,l,r) != r - l + 1)
            {
                int ret = r;
                while(l <= r)
                {
                    int mid = l + r >> 1;
                    if(get(1,1,n,mid,r) == (r - mid + 1))
                    {
                        ret = mid;
                        r = mid - 1;
                    }
                    else 
                        l = mid + 1;
                }
                return node[ret-1];
            }
        }
        if(!get(1,1,n,pos[v],pos[v]))
            return v;
        u = par[v];
    }
    return u;
}

void query(int id)
{
    int u = canh[id].fi;
    int v = canh[id].se;
    if(v == par[u])
        swap(u,v);
    int root = get_root(u);
    if(is_on[id])
        cur[v] = old[v] = cur[root];
    else 
        cur[root] += cur[v] - old[v];
    is_on[id] ^= 1;
    up(1,1,n,pos[v]);
    //if(id == 5) cout << root << ' ' << u << ' ' << v << ' ' << id << '\n';
}

void solve()
{
    g[0].pb(0);
    dfs(1,-1);
    hld(1,0);

    // FOR(i,1,n)
    // {
    //     cout << head[i] << ' ' << pos[i] << ' ' << par[i] << ' ' << i << '\n';
    // }

    FOR(i,1,n)
        cur[i] = 1;

    FOR(i,1,m)
    {
        int x;
        cin >> x;
        query(x);
    }
    FOR(i,1,q)
    {
        int x;
        cin >> x;
        cout << cur[get_root(x)] << '\n';
    }
}

void input()
{
    //freopen("TEST.INP", "r", stdin);
    //freopen("TEST.OUT", "w", stdout);
    cin >> n >> m >> q;
    FOR(i,1,n-1)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        canh[i] = {u,v};
    }
}

signed main()
{
    faster
    input();
    solve();
}

Compilation message

synchronization.cpp: In function 'void up(int, int, int, int)':
synchronization.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
synchronization.cpp: In function 'int get(int, int, int, int, int)':
synchronization.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < g[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~
synchronization.cpp: In function 'int get_root(int)':
synchronization.cpp:101:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |                     int mid = l + r >> 1;
      |                               ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8272 KB Output is correct
2 Correct 3 ms 8508 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 2 ms 8276 KB Output is correct
5 Correct 3 ms 8276 KB Output is correct
6 Correct 3 ms 8532 KB Output is correct
7 Correct 13 ms 9060 KB Output is correct
8 Correct 16 ms 9044 KB Output is correct
9 Correct 15 ms 9044 KB Output is correct
10 Correct 140 ms 14088 KB Output is correct
11 Correct 145 ms 14088 KB Output is correct
12 Correct 289 ms 21800 KB Output is correct
13 Correct 76 ms 14020 KB Output is correct
14 Correct 110 ms 13644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17192 KB Output is correct
2 Correct 105 ms 17736 KB Output is correct
3 Correct 150 ms 21324 KB Output is correct
4 Correct 137 ms 21324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8272 KB Output is correct
2 Correct 2 ms 8276 KB Output is correct
3 Correct 2 ms 8276 KB Output is correct
4 Correct 3 ms 8276 KB Output is correct
5 Correct 2 ms 8500 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 30 ms 9812 KB Output is correct
8 Correct 392 ms 22696 KB Output is correct
9 Correct 398 ms 22732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 19784 KB Output is correct
2 Correct 340 ms 22404 KB Output is correct
3 Correct 338 ms 22496 KB Output is correct
4 Correct 342 ms 22348 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8272 KB Output is correct
2 Correct 3 ms 8272 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 3 ms 8272 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 16 ms 9044 KB Output is correct
7 Correct 193 ms 14924 KB Output is correct
8 Correct 440 ms 22604 KB Output is correct
9 Correct 113 ms 15044 KB Output is correct
10 Correct 377 ms 14924 KB Output is correct
11 Correct 148 ms 19020 KB Output is correct
12 Correct 154 ms 19024 KB Output is correct
13 Correct 369 ms 22348 KB Output is correct