제출 #764900

#제출 시각아이디문제언어결과실행 시간메모리
764900vjudge1Roadside Advertisements (NOI17_roadsideadverts)C++17
100 / 100
174 ms18840 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) #define all(a) a.begin() , a.end() #define F first #define S second using namespace std; using ll = long long; const int N = 2e5+5 , inf = 2e9 + 7; const ll INF = 1e18 , mod = 1e9+7 ; 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); ll 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(){ ios; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...