Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
4.1 kB
1
Indexable
Never
#include <stdio.h>

#include <vector>

using namespace std;

#define MAXN 10005
#define rep(i, n) for (i = 0; i < (n); i++)

    struct Node {
        int parent, rank;
        vector < int > enemyList;
    }
nd[MAXN];

int n;

int findSet(int x) { //returns the root of node x
    if (nd[x].parent == x) return x;
    return nd[x].parent = findSet(nd[x].parent);
}

void setFriends(int x, int y) {
    x = findSet(x);
    y = findSet(y);
    if (x == y) return; //already friends
    int i;
    rep(i, nd[y].enemyList.size()) if (nd[y].enemyList[i] == x) { //already enemies
        printf("-1\n");
        return;
    }

    int j;
    if (nd[x].rank < nd[y].rank) { //y will be parent of x
        nd[x].parent = y;
        //transfer x's enemyList to y's
        rep(i, nd[x].enemyList.size()) {
            nd[y].enemyList.push_back(nd[x].enemyList[i]);
            //update the enemy's list - change x to y as y is the new root
            rep(j, nd[nd[x].enemyList[i]].enemyList.size()) {
                if (nd[nd[x].enemyList[i]].enemyList[j] == x) nd[nd[x].enemyList[i]].enemyList[j] = y;
            }
        }
        nd[x].enemyList.clear();
    } else if (nd[x].rank > nd[y].rank) { //x will be parent of y
        nd[y].parent = x;
        rep(i, nd[y].enemyList.size()) {
            nd[x].enemyList.push_back(nd[y].enemyList[i]);
            rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if (nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x;
        }
        nd[y].enemyList.clear();
    } else { //x & y same rank...so x will be parent of y with x's rank increasing by one
        nd[y].parent = x;
        rep(i, nd[y].enemyList.size()) {
            nd[x].enemyList.push_back(nd[y].enemyList[i]);
            rep(j, nd[nd[y].enemyList[i]].enemyList.size()) if (nd[nd[y].enemyList[i]].enemyList[j] == y) nd[nd[y].enemyList[i]].enemyList[j] = x;
        }
        nd[y].enemyList.clear();
        nd[x].rank++;
    }

}

void setEnemies(int x, int y) {
    x = findSet(x);
    y = findSet(y);
    if (x == y) { //already friends
        printf("-1\n");
        return;
    }
    int i;
    rep(i, nd[y].enemyList.size()) {
        if (nd[y].enemyList[i] == x) { //already enemies
            return;
        }
    }

    int j;
    //check if x & y both have a common enemy - that will be a contradiction
    rep(i, nd[x].enemyList.size()) {
        rep(j, nd[y].enemyList.size()) {
            if (nd[x].enemyList[i] == nd[y].enemyList[j]) {
                printf("-1\n");
                return;
            }
        }
    }

    //set all y's enemies as x's friends
    rep(i, nd[y].enemyList.size()) {
        setFriends(x, nd[y].enemyList[i]);
    }

    //set all x's enemies as y's friends
    rep(i, nd[x].enemyList.size()) {
        setFriends(nd[x].enemyList[i], y);
    }

    //do this as x & y's roots may have been changed
    x = findSet(x);
    y = findSet(y);

    nd[x].enemyList.push_back(y);
    nd[y].enemyList.push_back(x);
}

int main() {
    int i;
    int c, x, y;
    while (scanf(" %d", & n) == 1) {
        rep(i, n) nd[i].parent = i, nd[i].rank = 0, nd[i].enemyList.clear(); //make set
        while (scanf(" %d %d %d", & c, & x, & y) == 3) {
            if (c == 0) break;
            if (c == 1) { //set friends
                setFriends(x, y);
            } else if (c == 2) { //set enemies
                setEnemies(x, y);
            } else if (c == 3) { //are friends
                x = findSet(x);
                y = findSet(y);
                if (x == y) printf("1\n");
                else printf("0\n");
            } else { //are enemies
                x = findSet(x);
                y = findSet(y);
                rep(i, nd[x].enemyList.size()) if (nd[x].enemyList[i] == y) {
                    printf("1\n");
                    break;
                }
                if (i == nd[x].enemyList.size()) printf("0\n");
            }
        }
        //printf("\n");
    }
    return 0;
}