제출 #1290384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290384		lambd47	동기화 (JOI13_synchronization)	C++20	100 / 100	913 ms	24264 KiB

synchronization

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MX=1e5+7;
int n,m;
int seg[4*MX],pai[MX];
int edLow[MX];
vector<pair<int,int>> adj[MX];
int tam[MX];

void update(int pos, int ini, int fim, int id){//posso mudar para perssegs e fazer o(nlog) mas mo preguica
    if(ini>id || fim<id)return;
    if(ini==fim){
        seg[pos]^=1;
        return;
    }
    int m=(ini+fim)/2;
    update(2*pos,ini,m,id);
    update(2*pos+1,m+1,fim,id);
    seg[pos]=seg[2*pos]+seg[2*pos+1];
}
int query(int pos, int ini, int fim, int l, int r){
    if(ini>r || fim<l)return 0;
    if(l<= ini && fim<=r)return seg[pos];
    int m=(ini+fim)/2;
    return query(2*pos,ini,m,l,r)+query(2*pos+1,m+1,fim,l,r);
}
int findTop(int l, int r){
    if(l==r)return l;
    int m=(l+r)/2;
    if(query(1,0,n,m+1,r)==r-m)return findTop(l,m);
    return findTop(m+1,r);
}

int dfstam(int node){
    tam[node]=1;
    for(auto [a,ide]:adj[node]){
        if(tam[a]!=0)continue;
        pai[a]=node;
        edLow[ide]=a;
        tam[node]+=dfstam(a);
    }
    return tam[node];
}
int head[MX];
int id[MX];
int tmp;
vector<int> dfsOrd;
void hld(int node,int h){
    dfsOrd.push_back(node);
    id[node]=tmp++;
    head[node]=h;
    int hc=-1,peso=-1;
    for(auto [a,_]:adj[node]){
        if(a==pai[node])continue;
        if(peso<tam[a]){
            hc=a;
            peso=tam[a];
        }
    }
    if(hc==-1)return;
    hld(hc,h);
    for(auto [a,_]:adj[node]){
        if(a==hc || a==pai[node])continue;
        hld(a,a);
    }
}
int findGoat(int node){
    int x=query(1,0,n,id[head[node]],id[node]);
    if(x==0)return node;
    if(x==(id[node]-id[head[node]]+1))return findGoat(pai[head[node]]);
    return dfsOrd[findTop(id[head[node]],id[node])];
}
int arr[MX];
int brr[MX];


void update(int node){
    int tipo=query(1,0,n,id[node],id[node]);
    if(tipo==1){//on e vai pra off
        arr[node]=arr[findGoat(node)];
        brr[node]=arr[node];
        update(1,0,n,id[node]);
    }
    else{
        update(1,0,n,id[node]);
        arr[findGoat(node)]+=arr[node]-brr[node];
        brr[node]=arr[node];
    }
}

void solve() {
    adj[0].push_back({1,0});
    tmp=0;
    int q;
    cin>>n>>m>>q;
    L(i,1,n){
        arr[i]=1;
        brr[i]=0;
    }
    L(i,1,n-1){
        int a,b;cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    dfstam(0);
    hld(1,1);
    L(i,0,m-1){
        int a;cin>>a;
        update(edLow[a]);
    }
    R(i,n-1,0){
        int at=dfsOrd[i];
        if(query(1,0,n,id[at],id[at]))update(at);
    }
    //L(i,1,n)cout<<arr[i]<<" "<<brr[i]<<"\n";
    while(q--){
        int a;cin>>a;
        cout<<arr[a]<<"\n";
    }



}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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