Submission #234950

#	Time	Username	Problem	Language	Result	Execution time	Memory
234950		anonymous	Game (IOI14_game)	C++14	0 / 100	5 ms	464 KiB

game

#include "game.h"
#include <iostream>
#define MAXN 1505
using namespace std;
int Num[MAXN], N;
bool can[MAXN][MAXN];
class DSU {
public:
    int Set[MAXN];
    void init(int n) {
        for (int i=0; i<=n; i++) {Set[i] = i;}
    }
    int Find(int x) {
        return(Set[x] == x ? x : Set[x] = Find(Set[x]));
    }
    void Union(int x, int y) {
        int p1 = Find(x), p2 = Find(y);
        Set[p1] = p2;
        Num[p2] = 0;
        for (int i=0; i<N; i++) {
            if (Find(i) == p2) {can[p2][i] = 0;}
            else {can[p2][i] |= can[p1][i];}
            Num[p2] += can[p2][i];
            //printf("DEBUG %d %d %d\n",p2,i,can[p2][i]);
        }
    }
} UF;

void initialize(int n) {
    UF.init(n), N=n;
    for (int i=0; i<n; i++) {
        Num[i]= n-1;
        for (int j=0; j<n; j++) {
            can[i][j] = i != j;
        }
    }
}

int hasEdge(int u, int v) {
    int U = UF.Find(u), V = UF.Find(v);
    if (U == V) {return(0);}
    if (Num[U] == 1 || Num[V] == 1) {
        UF.Union(u,v);
        return(1);
    } else {
        Num[U ] -= 1;
        Num[V ] -= 1;
        can[U][V] = can[V][U] = 0;
        return(0);
    }
}

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