Editorial for Lubenica
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include<iostream> #include<algorithm> #define fr(a,b,c) for(a=b;a<=c;a++) #define frr(a,b,c) for(a=b;a>=c;a--) #define maxn 100100 #define oo 1000000000 using namespace std; int n,b[maxn][3],p[maxn],a[maxn*2],c[maxn*2],d[maxn],e[maxn][18],f[maxn][18],g[maxn][18],h[maxn],u,v,hh; void visit(int x,int y,int v,int u) { d[x]=v; h[x]=u; e[x][0]=y; hh=max(hh,u); int i; fr(i,p[x]+1,p[x+1]) if (a[i]!=y) visit(a[i],x,c[i],u+1); } void query(int x,int y) { int lg,t,i; v=oo,u=-oo; if (h[x]<h[y]) swap(x,y); for (lg=0;1<<lg<=h[x];lg++); lg--; frr(i,lg,0) if (h[x]-(1<<i)>=h[y]) { u=max(u,f[x][i]); v=min(v,g[x][i]); x=e[x][i]; } if (x==y) return; frr(i,lg,0) if (e[x][i] && e[x][i]!=e[y][i]) { u=max(u,max(f[x][i],f[y][i])); v=min(v,min(g[x][i],g[y][i])); x=e[x][i]; y=e[y][i]; } u=max(u,max(d[x],d[y])); v=min(v,min(d[x],d[y])); } int main() { int i,j,q,x,y; scanf("%d",&n); fr(i,1,n-1) { fr(j,0,2) scanf("%d",&b[i][j]); p[b[i][0]]++; p[b[i][1]]++; } fr(i,2,n+1) p[i]+=p[i-1]; fr(i,1,n-1) { a[p[b[i][0]]]=b[i][1]; c[p[b[i][0]]--]=b[i][2]; a[p[b[i][1]]]=b[i][0]; c[p[b[i][1]]--]=b[i][2]; } //pre-compute visit(1,0,0,0); fr(i,2,n) f[i][0]=g[i][0]=d[i]; for (j=1;1<<j<=hh;j++) fr(i,1,n) if (e[i][j-1]) { e[i][j]=e[e[i][j-1]][j-1]; f[i][j]=max(f[i][j-1],f[e[i][j-1]][j-1]); g[i][j]=min(g[i][j-1],g[e[i][j-1]][j-1]); } //query scanf("%d",&q); while (q--) { scanf("%d%d",&x,&y); query(x,y); printf("%d %d\n",v,u); //system("pause"); } return 0; }
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<climits> using namespace std; #define TR(v,i) for(typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 1e5 + 2, LOGN = 17 + 2; int P[N][LOGN], L[N], Wmin[N][LOGN], Wmax[N][LOGN], n; vector<vector<pair<int, int> > > g; void dfs(int u) { TR(g[u], it) { int v = it->first, w = it->second; if(v != P[u][0]) { P[v][0] = u; L[v] = L[u] + 1; Wmin[v][0] = Wmax[v][0] = w; dfs(v); } } } void init() { memset(P, -1, sizeof P); dfs(0); for(int j = 1; 1 << j < n; ++j) for(int u = 0; u < n; ++u) if(P[u][j-1] != -1) { P[u][j] = P[P[u][j-1]][j-1]; Wmin[u][j] = min(Wmin[u][j-1], Wmin[P[u][j-1]][j-1]); Wmax[u][j] = max(Wmax[u][j-1], Wmax[P[u][j-1]][j-1]); } } void query(int u, int v) { if(L[u] < L[v]) swap(u, v); int log = 0; for(; 1 << log <= L[u]; ++log); --log; int wmin = INT_MAX, wmax = INT_MIN; for(int i = log; i >= 0; --i) if(L[u] - (1 << i) >= L[v]) { wmin = min(wmin, Wmin[u][i]); wmax = max(wmax, Wmax[u][i]); u = P[u][i]; } if(u != v) { for(int i = log; i >= 0; --i) if(P[u][i] != P[v][i]) { wmin = min(wmin, min(Wmin[u][i], Wmin[v][i])); wmax = max(wmax, max(Wmax[u][i], Wmax[v][i])); u = P[u][i]; v = P[v][i]; } wmin = min(wmin, min(Wmin[u][0], Wmin[v][0])); wmax = max(wmax, max(Wmax[u][0], Wmax[v][0])); } printf("%d %d\n", wmin, wmax); } void enter() { scanf("%d", &n); g.resize(n); for(int i = 1; i < n; ++i) { int u, v, w; scanf("%d%d%d",&u,&v,&w); g[--u].push_back(make_pair(--v, w)); g[v].push_back(make_pair(u, w)); } } void solve() { int k; scanf("%d", &k); while(k--) { int u, v; scanf("%d%d",&u,&v); query(--u, --v); } } int main() { enter(); init(); solve(); return 0; }
Code mẫu của ladpro98
program lubenica; uses math; type e=record v,w,link:longint; end; const maxn=100009; fi=''; var adj:array[0..2*maxn] of e; head,q,d,cha,w:array[0..maxn] of longint; b,mi,ma:array[0..maxn,0..40] of longint; check:array[0..maxn] of boolean; inp:text; n,m,log,k,tt,res,u,v,r1,r2:longint; procedure input; var //inp:text; i,x,y,w:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n-1 do begin readln(inp,x,y,w); inc(m); adj[m].v:=y; adj[m].w:=w; adj[m].link:=head[x]; head[x]:=m; inc(m); adj[m].v:=x; adj[m].w:=w; adj[m].link:=head[y]; head[y]:=m; end; readln(inp,k); end; procedure init; var l,r,i,u,j:longint; v:e; begin l:=1;r:=1; q[1]:=1; d[1]:=0; check[1]:=true; while l<=r do begin u:=q[l];inc(l); i:=head[u]; while i>0 do begin v:=adj[i]; if (not check[v.v]) then begin check[v.v]:=true; inc(r); q[r]:=v.v; d[v.v]:=d[u]+1; cha[v.v]:=u; w[v.v]:=v.w; end; i:=v.link; end; end; log:=trunc(ln(n)/ln(2))+1; for i:=0 to n do begin b[i,0]:=cha[i]; ma[i,0]:=w[i]; mi[i,0]:=w[i]; for j:=1 to log do b[i,j]:=-1; end; for j:=1 to log do for i:=0 to n do begin b[i,j]:=b[b[i,j-1],j-1]; mi[i,j]:=min(mi[i,j-1],mi[b[i,j-1],j-1]); ma[i,j]:=max(ma[i,j-1],ma[b[i,j-1],j-1]); end; end; function getbit(i,j:longint):longint; begin exit(i shr (j-1) and 1); end; procedure lca(u,v:longint); var t,i:longint; begin res:=0; if d[u]>=d[v] then begin if d[u]>d[v] then begin t:=d[u]-d[v]; for i:=log downto 1 do if getbit(t,i)=1 then begin r1:=min(r1,mi[u,i-1]); r2:=max(r2,ma[u,i-1]); u:=b[u,i-1]; end; end; if u=v then exit; for i:=log downto 0 do if b[u,i]<>b[v,i] then begin r1:=min(r1,min(mi[u,i],mi[v,i])); r2:=max(r2,max(ma[u,i],ma[v,i])); u:=b[u,i]; v:=b[v,i]; end; if b[u,0]=b[v,0] then begin r1:=min(r1,min(mi[u,0],mi[v,0])); r2:=max(r2,max(ma[u,0],ma[v,0])); end; end else lca(v,u); end; begin input; init; for tt:=1 to k do begin readln(inp,u,v); r1:=high(longint);r2:=0; lca(u,v); writeln(r1,' ',r2); end; end.
Code mẫu của RR
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cerr << #x << " = " << (x) << endl; } #define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; } #define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; } #define sqr(x) ((x) * (x)) #define ll long long using namespace std; const int MN = 100111; const int INF = 1e9; int n; // number of vertices vector<int> a[MN]; // adjacency list vector<int> cost[MN]; const int MAX_LOG = 18; int father[MAX_LOG + 1][MN]; int nn[MAX_LOG + 1][MN]; int ln[MAX_LOG + 1][MN]; struct LCA { // Index from 1 int depth[MN]; public: LCA(int root) { depth[root] = 1; father[0][root] = -1; dfs(root, -1); FOR(i,1,MAX_LOG) { FOR(u,1,n) { // Change this if index from 0 int x = father[i-1][u]; if (x < 0) { father[i][u] = -1; nn[i][u] = INF; ln[i][u] = -INF; } else { father[i][u] = father[i-1][x]; nn[i][u] = min(nn[i-1][u], nn[i-1][x]); ln[i][u] = max(ln[i-1][u], ln[i-1][x]); } } } } pair<int,int> get(int u, int v) { pair<int,int> res = make_pair(INF, -INF); if (u == v) return res; if (depth[u] > depth[v]) swap(u, v); if (depth[u] != depth[v]) { FORD(i,MAX_LOG,0) { int x = father[i][v]; if (x < 0) continue; if (depth[x] >= depth[u]) { res.first = min(res.first, nn[i][v]); res.second = max(res.second, ln[i][v]); v = x; } } } if (u == v) return res; FORD(i,MAX_LOG,0) { if (father[i][u] != father[i][v]) { res.first = min(res.first, min(nn[i][u], nn[i][v])); res.second = max(res.second, max(ln[i][u], ln[i][v])); u = father[i][u]; v = father[i][v]; } } res.first = min(res.first, min(nn[0][u], nn[0][v])); res.second = max(res.second, max(ln[0][u], ln[0][v])); return res; } private: void dfs(int u, int fu) { REP(id,a[u].size()) { int v = a[u][id]; if (v == fu) continue; int c = cost[u][id]; depth[v] = depth[u] + 1; father[0][v] = u; nn[0][v] = c; ln[0][v] = c; dfs(v, u); } } }; int main() { ios :: sync_with_stdio(false); while (cin >> n) { FOR(i,1,n) { a[i].clear(); cost[i].clear(); } FOR(i,2,n) { int u, v, c; cin >> u >> v >> c; a[u].push_back(v); cost[u].push_back(c); a[v].push_back(u); cost[v].push_back(c); } LCA lca(1); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; auto res = lca.get(u, v); cout << res.first << ' ' << res.second << '\n'; } } }
Code mẫu của ll931110
{$MODE DELPHI} program LUBENICA; uses math; const input = ''; output = ''; maxn = 100003; maxv = 1000001; type pnode = ^tnode; tnode = record val,cost: integer; link: pnode; end; plist = ^tlist; tlist = record val,nlist: integer; link: plist; end; var n,k: integer; fi,fo: text; a: array[1..maxn] of pnode; b,c: array[1..4 * maxn] of integer; list,newlist: array[1..maxn] of plist; anc,anclist,trace: array[1..maxn] of integer; t1,t2,pre,rank: array[1..maxn] of integer; minlist,maxlist: array[1..2 * maxn] of integer; free,col: array[1..maxn] of boolean; num,ta,tb,tmin,tmax: integer; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure add(u,v,c: integer); var p: pnode; begin new(p); p^.val := v; p^.cost := c; p^.link := a[u]; a[u] := p; end; procedure addlist(u,v,i: integer); var p: plist; begin new(p); p^.val := v; p^.nlist := i; p^.link := list[u]; list[u] := p; end; procedure init; var i,u,v,c: integer; begin readln(fi, n); for i := 1 to n - 1 do begin readln(fi, u, v, c); add(u,v,c); add(v,u,c); end; readln(fi, k); for i := 1 to k do begin readln(fi, u, v); t1[i] := u; t2[i] := v; addlist(u,v,i); addlist(v,u,i); end; end; procedure makeset(x: integer); begin pre[x] := x; rank[x] := 0; free[x] := false; end; function findset(u: integer): integer; begin if u <> pre[u] then pre[u] := findset(pre[u]); findset := pre[u]; end; procedure link(u,v: integer); begin if rank[u] > rank[v] then pre[v] := u else pre[u] := v; if rank[u] = rank[v] then inc(rank[v]); end; procedure union(u,v: integer); begin link(findset(u),findset(v)); end; procedure LCA(u: integer); var p: pnode; q: plist; v: integer; begin makeset(u); anc[findset(u)] := u; p := a[u]; while p <> nil do begin v := p^.val; if free[v] then begin LCA(v); union(u,v); anc[findset(u)] := u; end; p := p^.link; end; col[u] := true; q := list[u]; while q <> nil do begin v := q^.val; if col[v] then anclist[q^.nlist] := anc[findset(v)]; q := q^.link; end; end; procedure update(i,low,high,x: integer); var mid: integer; begin if low = high then begin if low = num then begin b[i] := x; c[i] := x; end; exit; end; mid := (low + high) div 2; if num <= mid then update(2 * i,low,mid,x) else update(2 * i + 1,mid + 1,high,x); b[i] := min(b[2 * i],b[2 * i + 1]); c[i] := max(c[2 * i],c[2 * i + 1]); end; procedure answer(i,low,high: integer); var mid: integer; begin if (tb < low) or (high < ta) then exit; if (ta <= low) and (high <= tb) then begin if tmin > b[i] then tmin := b[i]; if tmax < c[i] then tmax := c[i]; exit; end; mid := (low + high) div 2; answer(2 * i,low,mid); answer(2 * i + 1,mid + 1,high); end; procedure calc(u: integer); var p: pnode; q: plist; v,tlist: integer; begin free[u] := false; inc(num); trace[u] := num; p := a[u]; while p <> nil do begin v := p^.val; if free[v] then begin update(1,1,n,p^.cost); calc(v); dec(num); end; p := p^.link; end; q := newlist[u]; tb := trace[u]; dec(tb); while q <> nil do begin v := q^.val; ta := trace[v]; tmin := maxv; tmax := -maxv; tlist := q^.nlist; if ta <= tb then answer(1,1,n); minlist[tlist] := tmin; maxlist[tlist] := tmax; q := q^.link; end; end; procedure addnewlist(u,v,i: integer); var p: plist; begin new(p); p^.val := v; p^.nlist := i; p^.link := newlist[u]; newlist[u] := p; end; procedure query; var i: integer; begin fillchar(col, sizeof(col), false); fillchar(free, sizeof(free), true); LCA(1); for i := 1 to k do begin addnewlist(t1[i],anclist[i],2 * i); addnewlist(t2[i],anclist[i],2 * i + 1); end; for i := 1 to 4 * maxn do begin b[i] := maxv; c[i] := -maxv; end; num := 0; fillchar(free, sizeof(free), true); calc(1); end; procedure printresult; var i: integer; begin for i := 1 to k do begin write(fo, min(minlist[2 * i],minlist[2 * i + 1]), ' '); writeln(fo, max(maxlist[2 * i],maxlist[2 * i + 1])); end; end; procedure closefile; begin close(fo); close(fi); end; begin openfile; init; query; printresult; closefile; end.
Code mẫu của skyvn97
#include<cstdio> #include<vector> #include<queue> #define MAX 100100 #define f first #define s second using namespace std; typedef pair<int,int> ii; struct row { int p,mx,mn; row(){} row(const int &_p,const int &_mx,const int &_mn) { p=_p;mx=_mx;mn=_mn; } }; vector<ii> g[MAX]; int c[MAX]; int l[MAX]; row p[MAX][21]; int n,k; void loadgraph(void) { scanf("%d",&n); int i,j,u,v,w; for (i=1;i<=n;i=i+1) { c[i]=0; l[i]=0; g[i].clear(); for (j=0;j<=19;j=j+1) p[i][j]=row(0,0,0); } l[0]=-1; for (i=1;i<n;i=i+1) { scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); g[u].push_back(ii(v,w)); g[v].push_back(ii(u,w)); } } void BFS(void) { queue<int> q; while (!q.empty()) q.pop(); c[1]=1; l[1]=0; q.push(1); int i,u; while (!q.empty()) { u=q.front();q.pop(); for (i=0;i<g[u].size();i=i+1) if (c[g[u][i].f]==0) { c[g[u][i].f]=1; l[g[u][i].f]=l[u]+1; p[g[u][i].f][0]=row(u,g[u][i].s,g[u][i].s); q.push(g[u][i].f); } } } int max(const int &x,const int &y) { if (x>y) return (x); else return (y); } int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } void process(void) { int i,j; BFS(); for (j=1;j<=19;j=j+1) for (i=1;i<=n;i=i+1) p[i][j]=row(p[p[i][j-1].p][j-1].p,max(p[i][j-1].mx,p[p[i][j-1].p][j-1].mx),min(p[i][j-1].mn,p[p[i][j-1].p][j-1].mn)); } row lca(int u,int v) { if (l[u]<l[v]) return (lca(v,u)); int i,mx,mn; mx=-1e7;mn=1e7; for (i=19;i>=0;i=i-1) if (l[p[u][i].p]>=l[v]) { mx=max(mx,p[u][i].mx); mn=min(mn,p[u][i].mn); u=p[u][i].p; } if (u==v) return (row(u,mx,mn)); for (i=19;i>=0;i=i-1) if (p[u][i].p!=p[v][i].p) { mx=max(mx,max(p[u][i].mx,p[v][i].mx)); mn=min(mn,min(p[u][i].mn,p[v][i].mn)); u=p[u][i].p; v=p[v][i].p; } return (row(p[u][0].p,max(mx,max(p[u][0].mx,p[v][0].mx)),min(mn,min(p[u][0].mn,p[v][0].mn)))); } void answer(void) { int i,a,b; row p; scanf("%d",&k); for (i=1;i<=k;i=i+1) { scanf("%d",&a); scanf("%d",&b); p=lca(a,b); printf("%d %d\n",p.mn,p.mx); } } int main(void) { loadgraph(); process(); answer(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <vector> using namespace std; int n; vector<int> ke[100010], gt[100010]; int fa[100010], tofa[100010], h[100010]; bool vs[100010]; int cha[17][100010], M[17][100010], m[17][100010]; void dfs(int i) { vs[i] = true; for(int k=0;k<ke[i].size();++k) { int j = ke[i][k], c = gt[i][k]; if(!vs[j]) { h[j] = h[i]+1; tofa[j] = c; fa[j] = i; dfs(j); } } } void init(int m[][100010], const int& (*f)(const int&,const int&)) { for(int i=1;i<=n;++i) m[0][i] = tofa[i]; for(int i=1;i<17;++i) { for(int j=1;j<=n;++j) m[i][j] = f( m[i-1][j], m[i-1][ cha[i-1][j] ] ); } } int chachung(int a,int b) { if(h[a]<h[b]) swap(a,b); for(int i=16;i>=0;--i) if( cha[i][a]>0 && h[cha[i][a]]>=h[b]) a = cha[i][a]; if(a==b) return a; for(int i=16;i>=0;--i) if( cha[i][a]>0 && cha[i][b]>0 && cha[i][a]!=cha[i][b]) { a = cha[i][a]; b = cha[i][b]; } return fa[a]; } int process(int u, int len, int m[][100010], const int& (*f)(const int&,const int&), int bd) { int res = bd; for(int i=16;i>=0;--i) if(len>=(1<<i)) { res = f( res, m[i][u]); u = cha[i][u]; len -= (1<<i); } return res; } int main() { scanf("%d", &n); for(int i=0;i<n-1;++i) { int u, v, c; scanf("%d%d%d", &u, &v, &c); ke[u].push_back(v); ke[v].push_back(u); gt[u].push_back(c); gt[v].push_back(c); } dfs(1); for(int i=1;i<=n;++i) cha[0][i] = fa[i]; for(int i=1;i<17;++i) for(int j=1;j<=n;++j) cha[i][j] = cha[i-1][ cha[i-1][j] ]; init( M, max<int>); init( m, min<int>); int q; scanf("%d", &q); for(int i=0;i<q;++i) { int u, v, c; scanf("%d%d", &u, &v); c = chachung(u,v); int m1 = max( process( u, h[u]-h[c], M, max<int>, 0), process( v, h[v]-h[c], M, max<int>, 0)); int m2 = min( process( u, h[u]-h[c], m, min<int>, 1000000), process( v, h[v]-h[c], m, min<int>, 1000000)); printf("%d %d\n", m2, m1); } //system("pause"); return 0; }
Comments