Submission #310489

#	Time	Username	Problem	Language	Result	Execution time	Memory
310489		lohacho	Game (IOI14_game)	C++14	100 / 100	539 ms	29688 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1504;
int way[NS][NS];
int NN;
struct dsu{
    vector < int > pr, rk;
    int N;
    dsu(){}
    dsu(int n):N(n){
        pr.resize(N), rk.resize(N);
        for(int i = 0; i < N; ++i) pr[i] = i, rk[i] = 1;
    }
    inline int get(int x){
        return x == pr[x] ? x : pr[x] = get(pr[x]);
    }
    inline bool unite(int x, int y){
        x = get(x), y = get(y);
        if(x != y){
            if(rk[x] < rk[y]) swap(x, y);
            for(int i = 0; i < NN; ++i){
                way[x][i] += way[y][i];
                way[i][x] += way[i][y];
            }
            pr[y] = x, rk[x] += rk[y];
            return true;
        }
        return false;
    }
}group(NS);
int chk[NS][NS];

void initialize(int n) {
    NN = n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            way[i][j] = 1;
        }
    }
}

int hasEdge(int u, int v) {
    if(u > v){
        swap(u, v);
    }
    int a = group.get(u), b = group.get(v);
    if(a == b){
        return chk[u][v];
    }
    if(way[a][b] >= 2){
        --way[a][b], --way[b][a];
        return 0;
    }
    else{
        chk[u][v] = 1;
        group.unite(a, b);
        return 1;
    }
}

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