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.

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

Please read the guidelines before commenting.


There are no comments at the moment.