Hướng dẫn giải của Police
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 happyboy99x
#include<bits/stdc++.h> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 1e5, LOG_N = 16; vector<int> g[N]; bool isCut[N]; int d[N], f[N], low[N], l[N], p[N][LOG_N+1], timed, comp[N], n; void dfs(int u, int c) { d[u] = low[u] = timed++; comp[u] = c; int nchild = 0; TR(g[u], v) if(d[*v] == -1) { l[*v] = l[u] + 1; p[*v][0] = u; ++nchild; dfs(*v, c); low[u] = min(low[u], low[*v]); if(low[*v] >= d[u] || (p[u][0] == -1 && nchild == 2)) isCut[u] = true; } else if(*v != p[u][0]) low[u] = min(low[u], d[*v]); f[u] = timed++; } bool isDescendant(int u, int v) { return d[u] >= d[v] && f[u] <= f[v]; } void precal() { for(int i = 1; 1 << i < n; ++i) for(int u = 0; u < n; ++u) if(p[u][i-1] != -1) p[u][i] = p[p[u][i-1]][i-1]; } int jump(int u, int x) { for(int i = 0; i <= LOG_N; ++i) if(x & 1 << i) u = p[u][i]; return u; } bool canGo(int x, int y, int z) { if(comp[x] != comp[y]) return false; if(comp[x] != comp[z]) return true; if(!isCut[z]) return true; if(!isDescendant(x, z) && !isDescendant(y, z)) return true; if(!isDescendant(x, z)) return canGo(y, x, z); int px = jump(x, l[x] - l[z] - 1); if(isDescendant(y, z)) { int py = jump(y, l[y] - l[z] - 1); return px == py || (low[px] < d[z] && low[py] < d[z]); } return low[px] < d[z]; } bool canGo(int x, int y, int u, int v) { if(comp[x] != comp[y]) return false; if(comp[x] != comp[u]) return true; if(!isDescendant(v, u)) return canGo(x, y, v, u); if(low[v] < d[v]) return true; return !(isDescendant(x, v) ^ isDescendant(y, v)); } void enter() { int m; cin >> n >> m; for(int i = 0; i < m; ++i) { int u, v; cin >> u >> v; --u; --v; g[u].push_back(v); g[v].push_back(u); } } void init() { memset(d, -1, sizeof d); for(int u = 0, c = 0; u < n; ++u) if(d[u] == -1) dfs(u, c++); } void print(bool x) { puts(x ? "yes" : "no"); } void query() { int q; cin >> q; for(int i = 0; i < q; ++i) { int u, v, t; cin >> t >> u >> v; --u; --v; if(t == 1) { int x, y; cin >> x >> y; --x; --y; print(canGo(u, v, x, y)); } else { int x; cin >> x; --x; print(canGo(u, v, x)); } } } int main() { ios::sync_with_stdio(false); enter(); init(); precal(); query(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 100005; const int oo = trunc(1e9); using namespace std; vector<int> a[N], child[N]; int par[N], low[N], dis[N], fin[N]; int n, m, q, Time; void Enter() { scanf("%d %d", &n, &m); int i, u, v; for(i=1; i<=m; i++) { scanf("%d %d", &u, &v); a[u].push_back(v); a[v].push_back(u); } scanf("%d", &q); } void DFS(int u) { dis[u] = ++Time; low[u] = oo; int i, v; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (v == par[u]) continue; if (par[v] == 0) { par[v] = u; child[u].push_back(v); DFS(v); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dis[v]); } fin[u] = ++Time; } bool isChild(int v, int u) { //is v a descendant of u return dis[u] <= dis[v] && fin[v] <= fin[u]; } int FindDad(int u, int v) { //find the child of u which is the ancestor of v int l = 0, r = child[u].size() - 1, x, k; while (l <= r) { m = (l + r) >> 1; x = child[u][m]; if (fin[x] < dis[v]) l = m + 1; if (fin[v] <= fin[x]) { k = m; r = m - 1; } } return child[u][k]; } bool Ans1() { int a, b, u, v; scanf("%d %d %d %d", &a, &b, &u, &v); if (isChild(u, v)) swap(u, v); if (par[v] != u) return true; if (low[v] < dis[v]) return true; //now u - v is a bridge //if a and b are (not) all descendants of v if (isChild(a, v) == isChild(b, v)) return true; return false; } bool Ans2() { int a, b, u, y, x; scanf("%d %d %d", &a, &b, &u); if (!isChild(a, u) && !isChild(b, u)) return true; if (isChild(a, u) && isChild(b, u)) { x = FindDad(u, a); y = FindDad(u, b); if (x == y) return true; if (low[x] < dis[u] && low[y] < dis[u]) return true; return false; } else { //suppose that a is in and b is out if (isChild(b, u)) swap(a, b); x = FindDad(u, a); if (low[x] < dis[u]) return true; return false; } } int main() { Enter(); int i, type; bool res; for(i=1; i<=n; i++) if (par[i] == 0) { par[i] = -1; DFS(i); } while (q--) { scanf("%d", &type); if (type == 1) res = Ans1(); else res = Ans2(); if (res) printf("yes\n"); else printf("no\n"); } return 0; }
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=100001; MAXQ=300001; type list=^node; node=record u:longint; next:list; end; var ds1,ds2,ke:array[1..MAXN] of list; h,father,getIn,getOut,low,reg,lab:array[1..MAXN] of longint; kq,g1,g2,a,b:array[1..MAXQ] of longint; count,q,n:longint; f1,f2:text; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure add(u:longint; var a:list); inline; var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure dfs1(u:longint); var p:list; v:longint; begin inc(count); getIn[u]:=count; low[u]:=count; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if h[v]>0 then begin if father[u]<>v then low[u]:=min(low[u],getIn[v]); continue; end; h[v]:=h[u]+1; father[v]:=u; dfs1(v); low[u]:=min(low[u],low[v]); end; inc(count); getOut[u]:=count; end; procedure inp; var yc,m,u,v:longint; begin read(f1,n,m); for m:=1 to m do begin read(f1,u,v); add(u,ke[v]); add(v,ke[u]); end; //dfs1 h[1]:=1; father[1]:=1; count:=0; dfs1(1); read(f1,q); for q:=1 to q do begin read(f1,yc); if yc=1 then begin read(f1,a[q],b[q],g1[q],g2[q]); if g2[q]=father[g1[q]] then swap(g1[q],g2[q]); add(q,ds1[g2[q]]); end else //yc=2 begin read(f1,a[q],b[q],g2[q]); add(q,ds2[g2[q]]); end; end; end; procedure ans; begin for q:=1 to q do if kq[q]=1 then writeln(f2,'no') else writeln(f2,'yes'); end; function getRoot(u:longint):longint; inline; begin if lab[u]<0 then exit(u) else begin lab[u]:=getRoot(lab[u]); exit(lab[u]); end; end; procedure union(r1,r2:longint); inline; begin if r1=r2 then exit; if lab[r1]<lab[r2] then begin lab[r1]:=lab[r1]+lab[r2]; lab[r2]:=r1; end else begin lab[r2]:=lab[r1]+lab[r2]; lab[r1]:=r2; end; if h[reg[r1]]<h[reg[r2]] then reg[r2]:=reg[r1] else reg[r1]:=reg[r2]; end; procedure ans1(g1,g2,u,v,i:longint); begin if g2=father[g1] then swap(g1,g2); if g1<>father[g2] then exit; if (getIn[g2]<=getIn[v]) and (getOut[v]<=getOut[g2]) then swap(u,v); if (getIn[g2]<=getIn[v]) and (getOut[v]<=getOut[g2]) then exit; if (getIn[u]<getIn[g2]) or (getOut[g2]<getOut[u]) then exit; if low[reg[getRoot(u)]]<getIn[g2] then exit; kq[i]:=1; end; procedure dfs2(u:longint); var p:list; v:longint; begin p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if father[v]=u then dfs2(v); end; p:=ds1[u]; while p<>nil do begin v:=p^.u; p:=p^.next; ans1(g1[v],g2[v],a[v],b[v],v); end; union(getRoot(u),getRoot(father[u])); end; procedure ans2(g,u,v,i:longint); var r1,r2:longint; begin if ((getIn[u]<getIn[g]) or (getOut[g]<getOut[u])) and ((getIn[v]<getIn[g]) or (getOut[g]<getOut[v])) then exit; if (getIn[u]<getIn[g]) or (getOut[g]<getOut[u]) then u:=1; if (getIn[v]<getIn[g]) or (getOut[g]<getOut[v]) then v:=1; r1:=reg[getRoot(u)]; r2:=reg[getRoot(v)]; if r1=r2 then exit; u:=low[r1]; v:=low[r2]; if (v<getIn[g]) and (u<getIn[g]) then exit; kq[i]:=1; end; procedure dfs3(u:longint); var p:list; v:longint; begin p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if father[v]=u then dfs3(v); end; p:=ds2[u]; while p<>nil do begin v:=p^.u; p:=p^.next; ans2(g2[v],a[v],b[v],v); end; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if father[v]=u then union(getRoot(u),getRoot(v)); end; end; procedure solve; var i:longint; begin //dfs2: tra loi query 1 for i:=1 to n do lab[i]:=-1; for i:=1 to n do reg[i]:=i; dfs2(1); //dfs3: tra loi query 2 for i:=1 to n do lab[i]:=-1; for i:=1 to n do reg[i]:=i; dfs3(1); end; begin openF; inp; solve; ans; closeF; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 100100 #define x first #define y second using namespace std; typedef pair<int,int> ii; vector<ii> g[MAX]; int lowb[MAX]; int numb[MAX]; int stab[MAX]; int finb[MAX]; int pb[MAX]; int lowc[MAX]; int numc[MAX]; int stac[MAX]; int finc[MAX]; int pc[MAX][19]; int lc[MAX]; int cv[MAX]; int nc[MAX]; bool blk[10*MAX]; int n,m,q; int cnt,tme; set<ii> bri; int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } int id(const int &x) { if (x%2==1) return (x+1); else return (x-1); } void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); int i,u,v; for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); g[u].push_back(ii(v,2*i-1)); g[v].push_back(ii(u,2*i)); } lc[0]=-1; bri.clear(); } void visit_bridge(const int &u) { //printf("visit %d\n",u); int i,v; cnt++; tme++; stab[u]=tme; numb[u]=cnt; lowb[u]=n+1; for (i=0;i<g[u].size();i=i+1) if (!blk[id(g[u][i].y)]) { v=g[u][i].x; blk[g[u][i].y]=true; if (numb[v]==0) { pb[v]=u; visit_bridge(v); //if (lowb[v]>numb[u]) bri.insert(ii(u,v)); lowb[u]=min(lowb[u],lowb[v]); } else lowb[u]=min(lowb[u],numb[v]); } tme++; finb[u]=tme; } void visit_cut(const int &u) { //printf("visit %d\n",u); int i,v; cnt++; tme++; stac[u]=tme; numc[u]=cnt; lowc[u]=n+1; nc[u]=0; for (i=0;i<g[u].size();i=i+1) { v=g[u][i].x; if (numc[v]==0) { nc[u]++; pc[v][0]=u; lc[v]=lc[u]+1; visit_cut(v); cv[u]=cv[u]||(lowc[v]>=numc[u]); lowc[u]=min(lowc[u],lowc[v]); } else lowc[u]=min(lowc[u],numc[v]); } tme++; finc[u]=tme; //printf("Finish %d\n",u); } void pre_setup(void) { //printf("Setup\n"); cnt=0; tme=0; int i,j; for (i=1;i<=n;i=i+1) if (numb[i]==0) visit_bridge(i); cnt=0; tme=0; //printf("123\n"); for (i=1;i<=n;i=i+1) if (numc[i]==0) { visit_cut(i); if (nc[i]<2) cv[i]=false; } //printf("123\n"); for (j=1;j<18;j=j+1) for (i=1;i<=n;i=i+1) pc[i][j]=pc[pc[i][j-1]][j-1]; } bool is_bridge(const int &u,const int &v) { if (u!=pb[v] && v!=pb[u]) return (false); //if (bri.find(ii(u,v))!=bri.end()) return (true); //if (bri.find(ii(v,u))!=bri.end()) return (true); if (u==pb[v] && lowb[v]>numb[u]) return (true); if (v==pb[u] && lowb[u]>numb[v]) return (true); //printf("%d %d is not bridge\n",u,v); return (false); } bool ischild(int sta[],int fin[],const int &u,const int &v) { if (u==v) return (true); if (sta[u]<sta[v] && fin[v]<fin[u]) return (true); return (false); } bool check_bridge(const int &u,const int &v,const int &w1,const int &w2) { //u,v is bridge if (!is_bridge(u,v)) return (true); //printf("%d %d is bridge\n",u,v); if (u==pb[v]) { if (ischild(stab,finb,v,w1) && !ischild(stab,finb,v,w2)) return (false); if (ischild(stab,finb,v,w2) && !ischild(stab,finb,v,w1)) return (false); return (true); } else { if (ischild(stab,finb,u,w1) && !ischild(stab,finb,u,w2)) return (false); if (ischild(stab,finb,u,w2) && !ischild(stab,finb,u,w1)) return (false); return (true); } } int parent(int u,int d) { int i; for (i=17;i>=0;i=i-1) if (d>=(1<<i)) { u=pc[u][i]; d=d-(1<<i); } return (u); } bool check_cut(const int &u,const int &v,const int &w) { if (!cv[w]) return (true); if (!ischild(stac,finc,w,u) && !ischild(stac,finc,w,v)) return (true); if (!ischild(stac,finc,w,u)) { int v1=parent(v,lc[v]-lc[w]-1); return (lowc[v1]<numc[w]); } if (!ischild(stac,finc,w,v)) { int u1=parent(u,lc[u]-lc[w]-1); return (lowc[u1]<numc[w]); } int u1=parent(u,lc[u]-lc[w]-1); int v1=parent(v,lc[v]-lc[w]-1); return (u1==v1 || (lowc[u1]<numc[w] && lowc[v1]<numc[w])); } void answer(void) { //printf("answer\n"); int i,t,u,v,w1,w2; scanf("%d",&q); for (i=1;i<=q;i=i+1) { scanf("%d",&t); scanf("%d",&u); scanf("%d",&v); if (t==1) { scanf("%d",&w1); scanf("%d",&w2); if (check_bridge(w1,w2,u,v)) printf("yes\n"); else printf("no\n"); } else { scanf("%d",&w1); if (check_cut(u,v,w1)) printf("yes\n"); else printf("no\n"); } } } int main(void) { #ifndef ONLINE_JUDGE freopen("tmp.txt","r",stdin); #endif loadgraph(); pre_setup(); answer(); return 0; }
Code mẫu của khuc_tuan
uses math; type integer = longint; type PNode = ^Node; Node = record i : integer; next : PNode; end; var c, j, cc, code, ds2, a, b, g1, g2, danhso, i, u, v, n, m, q : integer; ke : array[1..100000] of PNode; p : PNode; cao, post, low, num, scon, fa : array[1..100000] of integer; cha : array[0..17,1..100000] of integer; container : array[1..1000000] of Node; nct : integer; procedure dfs(i :integer); var p : Pnode; j : integer; begin p := ke[i]; scon[i] := 0; inc(danhso); num[i] := danhso; low[i] := danhso; while p<>nil do begin j := p^.i; if fa[j]=0 then begin fa[j] := i; inc( scon[i]); cao[j] := cao[i]+1; dfs(j); low[i] := min( low[i], low[j]); end else if j<>fa[i] then low[i] := min( low[i], num[j]); p := p^.next; end; inc( ds2); post[i] := ds2; end; procedure trao(var a,b:integer); var t : integer; begin t:=a;a:=b;b:=t; end; function chachung(a,b:integer):integer; var i : integer; begin if cao[a]<cao[b] then trao(a,b); for i:=17 downto 0 do if (cha[i,a]<>-1) and (cao[cha[i,a]]>=cao[b]) then a := cha[i,a]; if a=b then begin chachung :=a; exit; end; for i:=17 downto 0 do if cha[i,a]<>cha[i,b] then begin a:=cha[i,a]; b:=cha[i,b]; end; chachung := fa[a]; end; function thuoc(a,b,c:integer):boolean; begin thuoc := (num[a]<=num[c]) and (num[c]<=num[b]) and (post[a]>=post[c]) and (post[c]>=post[b]); end; procedure nhay(var a, b : integer); var i : integer; begin for i:=17 downto 0 do if (cha[i,a]<>-1) and (cao[cha[i,a]]>cao[b]) then a := cha[i,a]; end; var ok : boolean; begin read( n, m); for i:=1 to m do begin read(u,v); inc(nct); p := @container[nct]; //new(p); p^.i := v; p^.next := ke[u]; ke[u] := p; inc(nct); p := @container[nct]; //new(p); p^.i := u; p^.next := ke[v]; ke[v] := p; end; fa[1] := -1; dfs(1); for i:=1 to n do cha[0,i] := fa[i]; for i:=1 to 17 do begin for j:=1 to n do begin cc := cha[i-1,j]; if cc<>-1 then cc := cha[i-1,cc]; cha[i,j] := cc; end; end; read( q); for i:=1 to q do begin read(code); if code=1 then begin read( a, b, g1, g2); if (g1<>fa[g2]) and (g2<>fa[g1]) then writeln('yes') else begin if g2=fa[g1] then trao(g1, g2); if low[g2]<=num[g1] then writeln('yes') else begin cc := chachung( a, b); if (thuoc(cc,a,g1) or thuoc(cc,b,g1)) and (thuoc(cc,a,g2) or thuoc(cc,b,g2)) then writeln('no') else writeln('yes'); end; end; end else begin read( a, b, c); cc := chachung(a,b); if thuoc(cc,a,c) or thuoc( cc, b, c) then begin ok := true; if (fa[c]<>-1) and (thuoc(cc, a, fa[c]) or thuoc( cc, b, fa[c])) then if low[c]>num[fa[c]] then ok := false; if thuoc(cc, a, c) then begin nhay( a, c); if low[a]>=num[c] then ok := false; end; if thuoc( cc, b, c) then begin nhay( b, c); if low[b]>=num[c] then ok := false; end; if(ok) then writeln('yes') else writeln('no'); end else begin writeln('yes') end; end; end; end.
Bình luận