Участник:Rimon/Dynamic Tree Connectivity

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/DYNACON1/

C++(gcc 8.3)

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int maxn = 100005;
 
int n, m, pre[maxn];
 
inline int iread() {
    int f = 1, x = 0; char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return f * x;
}
 
inline void makeroot(int x) {
    for(int y = 0, fa = pre[x]; x; fa = pre[x = fa]) {
        pre[x] = y;
        y = x;
    }
}
 
inline bool check(int a, int b) {
    for(; a != b && b; b = pre[b]);
    return a == b;
}
 
int main() {
    n = iread(); m = iread();
    while(m--) {
        char ch = getchar(); for(; ch != 'a' && ch != 'r' && ch != 'c'; ch = getchar());
        int a = iread(), b = iread();
        makeroot(a);
        if(ch == 'a') pre[a] = b;
        else if(ch == 'r') pre[b] = 0;
        else printf(check(a, b) ? "YES\n" : "NO\n");
    }
    return 0;
}