Editorial for Nước lạnh


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.

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

const max=100000;
var n,m:longint;
    a:array[0..max,0..2] of longint;
    d,q:array[1..max] of longint;

procedure rf;
var i:longint;
begin
     readln(n,m);
     for i:=1 to m do readln(a[i,0],a[i,1],a[i,2]);
end;

procedure sort(l,r:longint);
var i,j,x:longint;
begin
     i:=l; j:=r; x:=a[(i+j) div 2,0];
     repeat
           while a[i,0]<x do i:=i+1;
           while x<a[j,0] do j:=j-1;
           if i<=j then
           begin
                a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if j>l then sort(l,j);
end;

function bs(p:longint):longint;
var l,r,mid:longint;
begin
     l:=1; r:=m;
     repeat
           mid:=(l+r) div 2;
           if a[mid,0]=p then break
           else
           begin
                if a[mid,0]<p then l:=mid+1
                else r:=mid-1;
           end;
     until l>r;
     if l>r then bs:=0
     else bs:=mid;
end;

procedure pr;
var i,j,num,c,t:longint;
begin
     sort(1,m);
     fillchar(d,sizeof(d),0);
     d[1]:=1;
     i:=a[1,1]; j:=a[1,2];
     d[i]:=2; d[j]:=2;
     q[1]:=i; q[2]:=j;
     num:=2; c:=1;
     repeat
           t:=bs(q[c]);
           if t>0 then
           begin
                q[num+1]:=a[t,1]; q[num+2]:=a[t,2];
                d[a[t,1]]:=d[q[c]]+1;
                d[a[t,2]]:=d[a[t,1]];
                num:=num+2;
           end;
           inc(c);
     until (c>num) or (num=n-1);
end;

procedure wf;
var i:longint;
begin
     for i:=1 to n do writeln(d[i]);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>

typedef struct {
    int l, h;
    int a[100005];
    void init() { l = 0; h = 0; }
    bool empty() { return l == h; }
    int size() { return h - l; }
    void push( int x ) { a[h++] = x; }
    int front() { return a[l]; }
    void pop() { ++l; }
} queue;

int g[100005][2];
int f[100005];
queue q;

int main() {
    int n, c;
    scanf( "%d%d", &n, &c );
    while(c--) {
        int u, v1, v2;
        scanf( "%d", &u );
        scanf( "%d%d", &g[u][0], &g[u][1] );
    }
    q.init(); q.push(1);
    for( int cnt = 1; q.empty() == false; ++cnt ) 
        for( int i = 0, _n = q.size(); i < _n; ++i ) {
            f[q.front()] = cnt;
            if ( g[q.front()][0] != 0 ) {
                q.push(g[q.front()][0]);
                q.push(g[q.front()][1]);
            }
            q.pop();
        }
    for( int i = 1; i <= n; ++i ) printf( "%d\n", f[i] );
    return 0;
}

Code mẫu của ladpro98

program vcoldwat;
uses    math;
type    e=record
                l,r:longint;
                isLeaf:boolean;
        end;
const   fi='';
        maxN=100000;

var     a:array[1..maxN] of e;
        res:array[1..maxN] of longint;
        isRoot:array[1..maxN] of boolean;
        n,root:longint;

procedure input;
var     inp:text;
        i,c,x,y,z:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,c);
        for i:=1 to n do
        begin
                a[i].isLeaf:=true;
                isRoot[i]:=true;
        end;
        for i:=1 to c do
        begin
                readln(inp,x,y,z);
                a[x].l:=min(y,z);
                a[x].r:=max(y,z);
                a[x].isLeaf:=false;
                isRoot[y]:=false;
                isRoot[z]:=false;

        end;
        close(inp);
end;

procedure back(i,k:longint);
begin
        res[i]:=k;
        if not a[i].isLeaf then
        begin
                back(a[i].l,k+1);
                back(a[i].r,k+1);
        end;
end;

procedure init;
var  i:longint;
begin
        for i:=1 to N do
        if isRoot[i] then
        begin
                root:=i;
                exit;
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to N do
        writeln(res[i]);
end;

begin
        input;
        init;
        back(root,1);
        output;
end.

Code mẫu của RR

type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  n,k,i,u,v1,v2:longint;
  ke:array[1..100111] of list;
  d:array[1..100111] of longint;

procedure dfs(u:longint);
    var
      p:list;
      v:longint;
    begin
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          d[v]:=d[u]+1;
          dfs(v);
        end;
    end;

begin
  read(n,k);
  for i:=1 to k do
    begin
      read(u,v1,v2);
      add(v1,ke[u]);
      add(v2,ke[u]);
    end;
  d[1]:=1;
  dfs(1);
  for i:=1 to n do
    writeln(d[i]);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
struct cay
  {
  long u,v;
  };
cay a[100000];
long f[100000]; 
void duyet(long n)
{
//printf("%ld",n);
if(a[n].u!=0)
  {
  f[a[n].u]=f[n]+1;
  f[a[n].v]=f[n]+1;
  duyet(a[n].u);
  duyet(a[n].v);
  }
}
main()
{
long n,m,x;
scanf("%ld %ld",&n,&m);
for(long i=1;i<=n;i++)
  {
  a[i].u=0;
  a[i].v=0;
  }
for(long i=1;i<=m;i++)
  {
  scanf("%ld",&x);
  scanf("%ld %ld",&a[x].u,&a[x].v);
  }
//printf("%ld %ld ",a[1].u,a[1].v);  
f[1]=1;
duyet(1);
for(long i=1;i<=n;i++)
  printf("%ld\n",f[i]);
//getch();
}

Code mẫu của ll931110

Program VCOLDWAT;
        Const
                input  = '';
                output = '';
        Var
                x,y,z,head,adj,trace: array[1..100000] of longint;
                                root: array[1..100000] of boolean;
                                 n,c: longint;

Procedure init;
          Var
                f: text;
                i: longint;
          Begin
                Fillchar(head, sizeof(head), 0);
                Fillchar(root, sizeof(root), true);

                Assign(f, input);
                        Reset(f);

                Readln(f, n, c);
                For i:= 1 to c do
                        Begin
                                Readln(f, x[i], y[i], z[i]);
                                head[x[i]]:= head[x[i]] + 2;
                        End;
                Close(f);

                For i:= 2 to n do head[i]:= head[i] + head[i - 1];
                head[n + 1]:= 2 * c;

                For i:= 1 to c do
                        Begin
                                adj[head[x[i]]]:= y[i];
                                dec(head[x[i]]);
                                root[y[i]]:= false;

                                adj[head[x[i]]]:= z[i];
                                dec(head[x[i]]);
                                root[y[i]]:= false;
                        End;
          End;

Procedure DFS(u: longint);
          Var
                v: longint;
          Begin
                For v:= head[u] + 1 to head[u + 1] do
                        if trace[adj[v]] = 0 then
                                Begin
                                        trace[adj[v]]:= trace[u] + 1;
                                        DFS(adj[v]);
                                End;
          End;

Procedure solve;
          Var
                  f: text;
                i,k: longint;
          Begin
                For i:= 1 to n do if root[i] then
                        Begin
                                k:= i;
                                break;
                        End;

                trace[k]:= 1;
                DFS(k);

                Assign(f, output);
                        Rewrite(f);
                        For i:= 1 to n do writeln(f, trace[i]);
                Close(f);
          End;

Begin
        init;
        solve;
End.

Code mẫu của skyvn97

#include<cstdio>
#include<queue>
#include<vector>
#define MAX   100100
using namespace std;
vector<int> g[MAX];
int l[MAX];
int c[MAX];
int n;
void loadgraph(void) {
    scanf("%d",&n);
    int i,k,e,b1,b2;
    scanf("%d",&k);
    for (i=1;i<=k;i=i+1) {
        scanf("%d",&e);
        scanf("%d",&b1);
        scanf("%d",&b2);
        g[e].push_back(b1);
        g[e].push_back(b2);
        g[b1].push_back(e);
        g[b2].push_back(e);
    }
    for (i=2;i<=n;i=i+1) c[i]=0;
}
void BFS(void) {
    int i,x;
    queue<int> q;
    q.push(1);
    c[1]=1;
    l[1]=1;
    while (!q.empty()) {
        x=q.front();q.pop();
        for (i=0;i<g[x].size();i=i+1)
            if (c[g[x][i]]==0) {
                c[g[x][i]]=1;
                l[g[x][i]]=l[x]+1;
                q.push(g[x][i]);
            }
    }
}
void process(void) {
    int i;
    for (i=1;i<=n;i=i+1) printf("%d\n",l[i]);
}
int main(void) {
    loadgraph();
    BFS();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <cstdio>
#include <vector>

using namespace std;

vector<int> ke[100000];
int n, h[100000];

void dfs(int i) {
    for(int k=0;k<ke[i].size();++k) {
        int j = ke[i][k];
        h[j] = h[i]+1;
        dfs(j); 
    }   
}

int main() {
    int c;
    scanf("%d%d", &n, &c);
    for(int i=0;i<c;++i) {
        int e, b1, b2;
        scanf("%d%d%d", &e, &b1, &b2);  
        ke[e].push_back( b1);
        ke[e].push_back( b2);
    }   
    h[1] = 1;
    dfs(1);
    for(int i=1;i<=n;++i) printf("%d\n", h[i]);
    //system("pause");
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.