Submission #298886

#	Time	Username	Problem	Language	Result	Execution time	Memory
298886		lakshith_	Game (IOI14_game)	C++14	42 / 100	1050 ms	2324 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define shit cout << "shit\n";

using namespace std;

struct subset{
    int parent;
    int rank;
};

subset subsets[1510];
int n;

int find(int x){
    if(subsets[x].parent==-1)return x;
    subsets[x].parent = find(subsets[x].parent);
    return subsets[x].parent;
}

void Union(int X,int Y){
    int x = find(X);
    int y = find(Y);
    if(subsets[x].rank<subsets[y].rank){
        subsets[x].parent = y;
    }else if(subsets[x].rank>subsets[y].rank){
        subsets[y].parent = x;
    }else{
        subsets[x].parent = y;
        subsets[y].rank++;
    }
}


bool flag[1501][1501];

void initialize(int N) {
    n=N;
    for(int i=0;i<n;i++){
        subsets[i] = {-1,1};
    }
}

bool getRemaining(int u,int v){
    vector<int> u_set,v_set;
    int U =find(u),V = find(v);
    for(int i=0;i<n;i++){
        int p = find(i);
        if(p==U)u_set.push_back(i);
        if(p==V)v_set.push_back(i);
    }
    int C = 0;

    // for(int a:u_set)
    // cout << a << "\t";
    // cout << endl;
    // for(int b:v_set)
    // cout << b << "\t";
    // cout << endl;

    for(int a:u_set){
        for(int b:v_set){
            if(!flag[a][b])C++;
            if(C>=2)return false;
        }
    }
    return true;
}

int hasEdge(int u, int v) {
    int r = 0;
    if(getRemaining(u,v))r=1;
    flag[u][v] =flag[v][u] = true;
    if(r==1)
    Union(u,v);
    return r;
}

// int main(){
//     int n,r;
//     cin >> n >> r;
//     initialize(n);
//     for(int i=0;i<r;i++){
//         int a,b;
//         cin >> a >> b;
//         cout << hasEdge(a,b) << "\n";
//     }
// }

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58