Submission #298928

#	Time	Username	Problem	Language	Result	Execution time	Memory
298928		lakshith_	Game (IOI14_game)	C++14	15 / 100	1 ms	384 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;
vector<vector<int>> setList(1501,vector<int>());

int find(int x){
    if(subsets[x].parent==x)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;
        setList.at(y).push_back(X);
    }else if(subsets[x].rank>subsets[y].rank){
        subsets[y].parent = x;
        setList.at(x).push_back(Y);
    }else{
        subsets[x].parent = y;
        subsets[y].rank++;
        setList.at(y).push_back(X);
    }
}


bool flag[1501][1501];

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

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);
    //     int p = subsets[i].parent;
    //     if(p==U)u_set.push_back(i);
    //     if(p==V)v_set.push_back(i);
    // }
    int C = 0;

    // for(int a:setList.at(U))
    // cout << a << "\t";
    // cout << endl;
    // for(int b:setList.at(V))
    // cout << b << "\t";
    // cout << endl;

    for(int a:setList.at(U)){
        for(int b:setList.at(V)){
            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;
}

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