Submission #1256792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256792		dssfsuper2	Game (IOI14_game)	C++20	100 / 100	262 ms	15932 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
    int n; vector<int> a;
    vector<vector<int>> nbtc;
    DSU(int N){
        n=N;
        a.assign(N, -1);
        nbtc.assign(N, vector<int>(N, 0));
    }
    int get(int x){return (a[x]<0 ? x:a[x]=get(a[x]));}
    bool connect(int u, int v){
        int x = get(u);
        int y = get(v);
        if(a[x]>a[y])swap(x, y);
        if(x==y)return false;
        int tts=a[x]*a[y];
        if(nbtc[x][y]<tts-1){
            nbtc[x][y]++;
            nbtc[y][x]++;
            return false;
        }
        else{
            a[x]+=a[y];
            a[y]=x;
            for(int i = 0;i<n;i++){
                nbtc[x][i]+=nbtc[y][i];
                nbtc[i][x]+=nbtc[i][y];
            }
            return true;
        }
    }
};
DSU m(1501);
void initialize(int n) {;
}

int hasEdge(int u, int v) {
    return (int)(m.connect(u, v));
}

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