Submission #301740

#	Time	Username	Problem	Language	Result	Execution time	Memory
301740		anonymous	Game (IOI14_game)	C++14	100 / 100	565 ms	16068 KiB

game

#include "game.h"
#include <iostream>
#define MAXN 1505
using namespace std;
int Cmp, N, adj[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;
        for (int i=0; i<N; i++) {
            if (Find(i) != y && i == Find(i)) {
                adj[i][p2] += adj[i][p1];
                adj[p2][i] += adj[i][p1];
            }
            adj[i][p1] = adj[p1][i] = 0;
        }
    }
} UF;

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

int hasEdge(int u, int v) {
    int p1 = UF.Find(u), p2 = UF.Find(v);
    if (p1 == p2) {return(1);}
    adj[p1][p2]--, adj[p2][p1]--;
    if (adj[p1][p2]) {
        return(0);
    }
    UF.Union(u,v);
    return(1);
}

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