Editorial for Robin
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
#include <iostream> #include <cstdio> using namespace std; int d[10010]; int get(int x) { if (d[x]-x) d[x]=get(d[x]); return d[x]; } int main() { int n,q,x,y,c; cin >> n >> q; for (int i=1;i<=n;i++) d[i]=i; for (int i=2;i<=n;i++) { y=i; scanf("%d%d",&x,&c); if (c==1) { x=get(x); y=get(y); if (x-y) d[y]=x; } } while (q--) scanf("%d%d",&x,&y), puts((get(x)==get(y)?"NO":"YES")); }
Code mẫu của ladpro98
program c11bc2; uses math; const maxn=22222; fi=''; var inp:text; a,adj,link,head:array[1..maxn] of longint; check:array[1..maxn] of boolean; n,m,c,i,x,y,p,k:longint; procedure dfs(i:longint); var j:longint; begin check[i]:=true; a[i]:=c; j:=head[i]; while j>0 do begin if not check[adj[j]] then dfs(adj[j]); j:=link[j]; end; end; begin assign(inp,fi);reset(inp); readln(inp,n,k); for i:=2 to n do begin readln(inp,x,p); if p=1 then begin inc(m); adj[m]:=x; link[m]:=head[i]; head[i]:=m; inc(m); adj[m]:=i; link[m]:=head[x]; head[x]:=m; end; end; for i:=1 to n do if not check[i] then begin inc(c); dfs(i); end; for i:=1 to k do begin readln(inp,x,y); if a[x]=a[y] then writeln('NO') else writeln('YES'); end; end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <iomanip> #include <bitset> #include <complex> #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define REP(i,a) for(int i = 0; i < a; ++i) #define MP make_pair #define PB push_back using namespace std; int lab[10111]; int getRoot(int u) { if (lab[u] < 0) return u; return lab[u] = getRoot(lab[u]); } void merge(int u, int v) { if (u == v) return ; int x = lab[u] + lab[v]; if (lab[u] < lab[v]) { lab[u] = x; lab[v] = u; } else { lab[v] = x; lab[u] = v; } } int main() { int n, m; scanf("%d%d", &n, &m); memset(lab, -1, sizeof lab); int v, k; FOR(u,2,n) { scanf("%d%d", &v, &k); if (k == 2) continue; merge(getRoot(u), getRoot(v)); } int u; FOR(i,1,m) { scanf("%d%d", &u, &v); if (getRoot(u) != getRoot(v)) puts("YES"); else puts("NO"); } return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //include<conio.h> #define ep 0.000000001 #define maxn 10011 #define oo 1000000000 #define ooo 1ll << 62 //#define mod 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define fi first #define se second #define max_size 4 double const PI=4*atan(1); typedef long long int64; using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int n, m, u, v, run, f[10011]; bool flag[10011] = {0}; vector<int> V[10011]; void duyet(int x){ f[x] = run; flag[x] = 1; for(int i = 0; i < V[x].size(); i++){ if(!flag[V[x][i]]) duyet(V[x][i]); } } int main(){ // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); scanf("%d %d",&n,&m); for(int i = 2; i <= n; i++){ scanf("%d %d",&u,&v); if(v != 2){ V[u].push_back(i); V[i].push_back(u); } } run = 0; for(int i = 1; i <= n; i++){ if(!flag[i]){ duyet(i); run++; } } // for(int i = 1; i <= n; i++) printf("%d ",f[i]); printf("\n"); for(int i = 0; i < m; i++){ scanf("%d %d",&u,&v); if(f[u]!=f[v]) printf("YES\n"); else printf("NO\n"); } // getch(); }
Code mẫu của skyvn97
#include<cstdio> #include<vector> #define MAX 10101 #define LOG 14 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) #define fi first #define se second using namespace std; vector<pair<int,int> > adj[MAX]; int h[MAX]; int par[MAX][LOG+1]; bool haveEdge[MAX][LOG+1]; int n,q; void loadtree(void) { scanf("%d%d",&n,&q); FOR(i,2,n) { int j,t; scanf("%d%d",&j,&t); adj[i].push_back(make_pair(j,t)); adj[j].push_back(make_pair(i,t)); } h[0]=-1; } void dfs(int u) { REP(i,adj[u].size()) if (adj[u][i].fi!=par[u][0]) { int v=adj[u][i].fi; h[v]=h[u]+1; par[v][0]=u; haveEdge[v][0]=adj[u][i].se==2; dfs(v); } } void setupLCA(void) { dfs(1); FOR(j,1,LOG) FOR(i,1,n) { par[i][j]=par[par[i][j-1]][j-1]; haveEdge[i][j]=haveEdge[i][j-1]||haveEdge[par[i][j-1]][j-1]; } } bool answer(int u,int v) { if (h[u]<h[v]) return (answer(v,u)); FORD(i,LOG,0) if (h[par[u][i]]>=h[v]) { if (haveEdge[u][i]) return (true); u=par[u][i]; } if (u==v) return (false); FORD(i,LOG,0) if (par[u][i]!=par[v][i]) { if (haveEdge[u][i]) return (true); if (haveEdge[v][i]) return (true); u=par[u][i]; v=par[v][i]; } return (haveEdge[u][0]||haveEdge[v][0]); } void process(void) { REP(zz,q) { int u,v; scanf("%d%d",&u,&v); printf("%s\n",answer(u,v)?"YES":"NO"); } } int main(void) { loadtree(); setupLCA(); process(); return 0; }
Comments