Submission #1062647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062647		oscar1f	Game (IOI14_game)	C++17	100 / 100	246 ms	20864 KiB

game

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

const int TAILLE_MAX=1500+5;
int nbSom;
int pere[TAILLE_MAX];
int taille[TAILLE_MAX];
int nbVu[TAILLE_MAX][TAILLE_MAX];

int find(int pos) {
    if (pos!=pere[pos]) {
        pere[pos]=find(pere[pos]);
    }
    return pere[pos];
}

void initialize(int n) {
    nbSom=n;
    for (int i=0;i<nbSom;i++) {
        pere[i]=i;
        taille[i]=1;
    }
}

int hasEdge(int deb, int fin) {
    deb=find(deb);
    fin=find(fin);
    nbVu[deb][fin]++;
    nbVu[fin][deb]++;
    if (nbVu[deb][fin]==taille[deb]*taille[fin]) {
        taille[deb]+=taille[fin];
        pere[fin]=deb;
        for (int i=0;i<nbSom;i++) {
            if (find(i)!=deb) {
                nbVu[i][deb]+=nbVu[i][fin];
            }
        }
        for (int j=0;j<nbSom;j++) {
            nbVu[deb][j]+=nbVu[fin][j];
        }
        return 1; 
    }
    else {
        return 0;
    }
}

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