제출 #1164242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164242		ChottuF	Roadside Advertisements (NOI17_roadsideadverts)	C++20	100 / 100	176 ms	18160 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+5;

int P[N] , D[N] , H[N] , B[N] , pos[N];
vector<int> g[N] ,vec;
int a[N] , b[N] , d[N] , c[N] , NW , t[N*4] , t1[N*4] , u[N*4];
int up[N][20] , n , sz[N];
void upd(int v, int tl, int tr , int pos , int val){
    u[v] = -1;
    if(tl == tr){
        t[v] = val;
        t1[v] = val;
        return;
    }
    int tm = (tl+tr) >> 1;
    if(tm >= pos) upd(v*2,tl,tm,pos,val);
    else upd(v*2+1,tm+1,tr,pos,val);
    t[v] = t[v*2]+t[v*2+1];
    t1[v] = t[v];
}
int lca(int a , int b){
    if(D[a] > D[b]) swap(a,b);
    for(int i = 19; i >= 0; i--){
        if(D[a] <= D[up[b][i]]){
            b = up[b][i];
        }
    }
    if(a == b) return a;
    for(int i = 19; i >= 0; i--){
        if(up[a][i] != up[b][i]){
            b = up[b][i];
            a = up[a][i];
        }
    }
    return up[a][0];
}
    
void dfs(int v , int pr){
    P[v] = pr;
    D[v] = D[pr]+1;
    int mx = 0;
    sz[v] = 1;
    up[v][0] = pr;
    for(int i = 1; i < 20; i++) up[v][i] = up[up[v][i-1]][i-1];
    for(int i : g[v]){
        int to = (v^a[i]^b[i]);
        if(to == pr) continue;
        dfs(to,v);
        d[to] = c[i];
        sz[v] += sz[to];
        if(sz[to] > mx){
            mx = sz[to];
            H[v] = to;
        }
    }
}	
void decompose(int v ,int h){
    B[v] = h;
    pos[v] = ++NW;
    if(H[v]) decompose(H[v],h);
    for(int i : g[v]){
        int to = (v^a[i]^b[i]);
        if(to != P[v] && to != H[v]) decompose(to,to);
    }
}
void push(int v , int tl , int tr){
    if(tl == tr || u[v] == -1) return;
    t[v*2] = t1[v*2] * u[v];
    t[v*2+1] = t1[v*2+1] * u[v];
    u[v*2] = u[v];
    u[v*2+1] = u[v];
    u[v] = -1;
}
int getsum(int v ,int tl , int tr , int l , int r){
    push(v,tl,tr);
    if(l <= tl && tr <= r) return t[v];
    if(tl > r || tr < l) return 0;
    int tm = (tl+tr) >> 1;
    return getsum(v*2,tl,tm,l,r) + getsum(v*2+1,tm+1,tr,l,r);
}
void updlr(int v, int tl , int tr , int l , int r, int val){
    push(v,tl,tr);
    if(l > r) return;
    if(l <= tl && tr <= r){
        u[v] = val;
        t[v] = t1[v]*u[v];
        return;
    } 
    if(tl > r || tr < l) return;
    int tm = (tl+tr) >> 1;
    updlr(v*2,tl,tm,l,r,val);
    updlr(v*2+1,tm+1,tr,l,r,val);
    t[v] = t[v*2] + t[v*2+1];
}
int get(int a , int b){
    int res = 0;
    for(; B[a] != B[b]; a = P[B[a]]){
        res += getsum(1,0,n,pos[B[a]],pos[a]);
        updlr(1,0,n,pos[B[a]],pos[a],0);
    }
    res += getsum(1,0,n,pos[b]+1,pos[a]);
    updlr(1,0,n,pos[b]+1,pos[a],0);
    return res;
}
void clr(int a , int b){
    for(; B[a] != B[b]; a = P[B[a]])  updlr(1,0,n,pos[B[a]],pos[a],1);
    updlr(1,0,n,pos[b]+1,pos[a],1);
}
void solve(){
    cin >> n;
    for(int i = 1; i < n;i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]++;	
        b[i]++;	
        g[a[i]].push_back(i);		
        g[b[i]].push_back(i);	
    }
    dfs(1,0);
    decompose(1,1);
    for(int i = 1; i <= n; i++) upd(1,0,n,pos[i],d[i]);
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++){
        int a , b , c , d, e;
        cin >> a >> b >> c >> d >> e;
        a++; b++; c++; d++; e++;
        int LCA = lca(a,b); LCA = lca(LCA,c); LCA = lca(LCA,d); LCA = lca(LCA,e);
        long long ans = get(a,LCA);
        ans += get(b,LCA);
        ans += get(c,LCA);
        ans += get(d,LCA);
        ans += get(e,LCA);
        cout << ans << "\n";
        clr(a,LCA);
        clr(b,LCA);
        clr(c,LCA);
        clr(d,LCA);
        clr(e,LCA);
    }
}

signed main(){
    solve();
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30