제출 #1356276

#제출 시각아이디문제언어결과실행 시간메모리
1356276luvwinter동기화 (JOI13_synchronization)C++20
100 / 100
244 ms34136 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
#define FOR(i , l , r) for(int i = (l) ; i <= (r) ; i++)
#define FOD(i , r , l) for(int i = (r) ; i >= (l) ; i--)
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define faster ios_base :: sync_with_stdio(false); cin.tie(NULL);
const int N = 2e5 + 5;
const int LOG = 19;
int cnt[N];
pii edges[N];
vector<int> adj[N];
int n , m , q;
int par[N][LOG];
int tin[N];
int tout[N];
int h[N];
int BIT[N];
int timer;
int onoff[N];
int ans[N];
int last[N];
void upd(int id , int v) {
     while(id <= timer) {
        BIT[id] += v;
        id += id & - id;
     }
}

int get(int id) {
     int ans = 0;
     while(id) {
        ans += BIT[id];
        id -= id & -id;
     }
     return ans;
}


void dfs(int u) {
     tin[u] = ++timer;
     for(auto v : adj[u]) {
          if(v == par[u][0]) continue;
          h[v] = h[u] + 1;
          par[v][0] = u;
          FOR(i , 1 , LOG - 1) {
              par[v][i] = par[par[v][i - 1]][i - 1];
          }
          dfs(v);
     }
     tout[u] = timer;

}

int find_par(int u) {
    FOD(i , LOG - 1, 0) {
        if(get(tin[par[u][i]]) == get(tin[u])){
            u = par[u][i];
        }
    }
    return u;
}




void solve () {
     cin >> n >> m >> q;
     FOR(i , 1 , n - 1) {
         cin >> edges[i].fi >> edges[i].se;
         adj[edges[i].fi].pb(edges[i].se);
         adj[edges[i].se].pb(edges[i].fi);
     }
     dfs(1);

     FOR(i , 1 , n) {
          ans[i] = 1;
          upd(tin[i] , -1);
          upd(tout[i] + 1 , +1);
     }

     FOR(i , 1 , m) {
         int id; cin >> id;
         int u = edges[id].fi;
         int v = edges[id].se;
         if(h[u] > h[v]) swap(u , v);
         if(!onoff[id]) {
            ans[find_par(u)] += ans[v] - last[v];
            upd(tin[v] , +1);
            upd(tout[v] + 1, -1);
         }
         else{
            ans[v] = last[v] = ans[find_par(u)];
            upd(tin[v] , -1);
            upd(tout[v] + 1 , +1);
         }
         onoff[id] ^= 1;

     }

     FOR(i , 1 , q) {
         int x; cin >> x; cout << ans[find_par(x)] << endl;
     }




}



main () {
   faster;
   solve();
   return 0;

}

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

synchronization.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main () {
      | ^~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…