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.
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