제출 #649068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
649068		AkiYuu	동기화 (JOI13_synchronization)	C++17	100 / 100	592 ms	23808 KiB

synchronization

/*

Author: AkiYuu
TASK:
LANG: C++14

*/

#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb push_back
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e5 + 5;
typedef pair<ll, ll> ii;

vector < int > a[mxn];
int now[mxn], last[mxn];
int up[20][mxn];
int n , m, q;
int tin[mxn], tout[mxn], timer = 0;
bool state[mxn];
int U[mxn], V[mxn];
int BIT[mxn];

void upd(int id, int v ){
    for(id; id <= n + 1; id += id & -id){
        BIT[id] += v;
    }
}

int sum(int id ){
    int res = 0;
    for ( id; id > 0; id -=  id & -id)
        res += BIT[id];
    return res;
}
void dfs(int u, int p){

    tin[u] = ++timer;


    up[0][u] = p;

    adj(v,a,u){
        if ( v == p ) continue;
        dfs(v,u);
    }

    tout[u] = timer;
}


int findlow(int u ){
    int ans = u;
    fbw(i,18,0) if ( sum(tin[up[i][ans]]) == sum(tin[u]) ) ans = up[i][ans];
    return ans;
}

void solve(){
    cin >> n >> m >> q;
    ffw(i,1,n-1){
        int u , v;
        cin >> u >> v;
        U[i] = u;
        V[i] = v;
        a[u].pb(v);
        a[v].pb(u);
    }
    dfs(1,1);

    ffw(k,1,18) ffw(i,1,n) {
        up[k][i] = up[k-1][ up[k-1][i] ];
    }

    ffw(i,1,n){
        now[i] = 1;
        last[i] = 0;
        state[i] = 0;
        upd(tin[i], 1);
        upd(tout[i] + 1, -1);
    }

    while(m--){
        int x;
        cin >> x;
        int u = U[x], v = V[x];
        if ( up[0][u] == v ) swap(u,v);
        if ( state[x] ) {
            now[v] = last[v] = now[ findlow(u) ];
            upd(tin[v], 1);
            upd(tout[v]+1, -1);
        }else {
            now[ findlow(u) ] += now[v] - last[v];
            upd(tin[v], -1);
            upd(tout[v] + 1, 1);
        }

        state[x] ^= 1;
    }

//    ffw(i,1,n) cout << now[i] << ' ';
//    cout << '\n';

    while(q--){

        int u; cin >> u;
        cout << now[ findlow(u) ] << '\n';

    }
}

int main(){
	fastio();
	int t = 1;
//	cin >> t;
	while (t--)
	solve();
}

컴파일 시 표준 에러 (stderr) 메시지

synchronization.cpp: In function 'void upd(int, int)':
synchronization.cpp:45:9: warning: statement has no effect [-Wunused-value]
   45 |     for(id; id <= n + 1; id += id & -id){
      |         ^~
synchronization.cpp: In function 'int sum(int)':
synchronization.cpp:52:11: warning: statement has no effect [-Wunused-value]
   52 |     for ( id; id > 0; id -=  id & -id)
      |           ^~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40