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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.