Submission #1096104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096104		HaciyevAlik	Game (IOI14_game)	C++14	100 / 100	222 ms	25256 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

const int mx = 1505;
int s[mx][mx];
int n;

struct DSU {
    vector<int> par;
    DSU(int n) {
        par.assign(n, -1);
    }
    int Find(int u) {
        if(par[u] < 0) return u;
        else return par[u] = Find(par[u]);
    }
    bool uni(int u,int v) {
        u = Find(u);
        v = Find(v);
        if(u != v) {
            if(par[u] > par[v]) {
                swap(u,v);
            }
            par[u] += par[v];
            par[v] = u;
            return true;
        } else {
            return false;
        }
    }
};

DSU dsu(mx);

void initialize(int N) {
    n = N;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(i == j) continue;
            s[i][j] = 1;
        }
    }
}


int hasEdge(int u, int v) {
    u = dsu.Find(u);
    v = dsu.Find(v);
    if(s[u][v] == 1) {
        dsu.uni(u,v);
        int w = dsu.Find(u);
        for(int i = 0; i < n; ++i) {
            if(dsu.par[i] < 0) {
                s[w][i] = s[i][w] = (s[u][i] + s[v][i]);
            }
        }
        return 1;
    } else {
        --s[u][v];
        --s[v][u];
        return 0;
    }
}

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