Submission #1103148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103148		khoile25108	Synchronization (JOI13_synchronization)	C++14	100 / 100	440 ms	22732 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40