제출 #1287117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287117		davele	Synchronization (JOI13_synchronization)	C++20	100 / 100	128 ms	18476 KiB

synchronization

#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "synchronization";
const int lim = 2e5, limit = lim+5;

int n, m, q;
vector <int> adj[limit];
int h[limit], par[limit], sz[limit];
int numchain, inchain[limit], head[limit];
int dshld[limit], lenhld, idhld[limit];
int BIT[limit];
int U[limit], V[limit];
int ans[limit], former[limit];
bool active[limit];

void dfs (int u, int pre){
    sz[u] = 1;
    for (int v:adj[u]){
        if (v==pre) continue;
        h[v] = h[u]+1;
        par[v] = u;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void heavize (int u, int pre){
    inchain[u] = numchain;
    dshld[++lenhld] = u;
    idhld[u] = lenhld;
    int nx = 0;
    for (int v:adj[u]){
        if (v==pre) continue;
        if (sz[v]>sz[nx]) nx = v;
    }
    if (nx!=0){
        heavize (nx, u);
    }
    for (int v:adj[u]){
        if (v!=pre && v!=nx){
            head[++numchain] = v;
            heavize (v, u);
        }
    }
}

void update (int id, int val){
    while (id<=n){
        BIT[id]+=val;
        id+=(id&(-id));
    }
}

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

int get (int l, int r){
    return get (r) - get(l-1);
}

void prep(){
    dfs(1, 1);
    head[++numchain] = 1;
    heavize (1, 1);
    for (int i=1; i<=n; i++) ans[i] = 1;
}

int finding (int u){
    int ori = u;
    // tim dinh cha cua u co do cao lon nhat ma value  = 0
    while (1){
        int L = idhld[head[inchain[u]]], R = idhld[u];
        int tot = R-L+1;
        if (get(L, R)==tot){
            u = par[head[inchain[u]]];
        }
        else{
//            cerr<<ori<<" "<<u<<"\n";
            //
            for (int i=20; i>=0; i--){
                if (R-MASK(i)+1>=L && get(R-MASK(i)+1, R)==MASK(i)){
                    R-=MASK(i);
                }
            }
            return dshld[R];
        }
    }
}

void changing (int id){
    int u = U[id], v = V[id];
    if (h[u]<h[v]) swap(u, v); // u la con v
    if (!active[id]){ // them canh nay
        int rootv = finding(v);
//        cerr<<id<<" them "<<u<<" "<<rootv<<"\n";
        ans[rootv] += ans[u] - former[u];
        update (idhld[u], 1);
    }
    else{ // xoa canh nay
        int rootv = finding(v);
//        cerr<<id<<" xoa "<<u<<" "<<rootv<<"\n";
        update (idhld[u], -1);
        ans[u] = ans[rootv];
        former[u] = ans[u];
    }
    active[id] = (!active[id]);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
    if (fopen((name+".inp").c_str(), "r")){
        freopen ((name+".inp").c_str(), "r", stdin);
        freopen ((name+".out").c_str(), "w", stdout);
    }
    //
    cin>>n>>m>>q;
    for (int i=1; i<n; i++){
        int u, v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
        U[i] = u; V[i] = v;
    }
    //
    prep();
    for (int i=1; i<=m; i++){
        int id;
        cin>>id;
        changing(id);
    }
    //
    for (int i=1; i<=q; i++){
        int u;
        cin>>u;
        cout<<ans[finding(u)]<<"\n";
    }
}

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

synchronization.cpp: In function 'int main()':
synchronization.cpp:188:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen ((name+".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:189:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen ((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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