oj.uz

답안 #1103132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103132 2024-10-20T08:53:36 Z khoile25108 동기화 (JOI13_synchronization) C++14
0 / 100
 501 ms 22604 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] > 0)
    {
        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(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) == (mid - r + 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);
    up(1,1,n,pos[v]);
    if(is_on[id])
        cur[v] = old[v] = cur[root];
    else 
        cur[root] += cur[v] - old[v];
    is_on[id] ^= 1;
    //cout << root << ' ' << u << ' ' << v << '\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:99:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 int mid = l + r >> 1;
      |                           ~~^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8276 KB Output is correct
2 Correct 2 ms 8276 KB Output is correct
3 Incorrect 2 ms 8276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 104 ms 17740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 501 ms 22604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8276 KB Output is correct
2 Correct 2 ms 8276 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Incorrect 2 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -