Submission #1237682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237682		inesfi	Game (IOI14_game)	C++20	100 / 100	221 ms	15868 KiB

game

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

const int TAILLEMAXI=1502;
int num_compo[TAILLEMAXI];
int nbliens[TAILLEMAXI][TAILLEMAXI];
int n;

void fusion(int a,int b){
    int nouv=num_compo[a];
    int anc=num_compo[b];
    for (int i=0;i<n;i++){
        if (num_compo[i]==anc){
            num_compo[i]=nouv;
        }
    }
    for (int i=0;i<n;i++){
        nbliens[i][nouv]+=nbliens[i][anc];
    }
    for (int i=0;i<n;i++){
        nbliens[nouv][i]+=nbliens[anc][i];
    }
}

void initialize(int a) {
    n=a;
    for (int i=0;i<n;i++){
        num_compo[i]=i;
        for (int j=0;j<n;j++){
            if (i!=j){
                nbliens[i][j]=1;
            }
        }
    }
}

int hasEdge(int a, int b) {
    if (num_compo[a]==num_compo[b]){
        return 0;
    }
    if (nbliens[num_compo[a]][num_compo[b]]>1){
        //cout<<nbliens[num_compo[a]][num_compo[b]]<<endl;
        nbliens[num_compo[a]][num_compo[b]]--;
        nbliens[num_compo[b]][num_compo[a]]--;
        return 0;
    }
    fusion(a,b);
    return 1;
}

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