Hướng dẫn giải của Lubenica
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận