제출 #237960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237960		nicolaalexandra	게임 (IOI14_game)	C++14	100 / 100	495 ms	25464 KiB

game

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

int n,i,t[DIM],a[DIM][DIM];

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

int hasEdge(int x, int y){
    x++, y++;
    int radx = get_rad(x), rady = get_rad(y);
    if (radx == rady)
        return 1;

    a[radx][rady]++, a[rady][radx]++;
    if (a[radx][rady] == (-t[radx]) * (-t[rady])){
        /// acum ar trebui sa unesc padurile astea
        if (t[radx] > t[rady])
            swap (radx,rady);

        t[radx] += t[rady];
        t[rady] = radx;

        /// trb sa actualizez matricea a
        for (int i=1;i<=n;i++){
            if (radx == i)
                continue;
            a[radx][i] += a[rady][i];
            a[i][radx] += a[rady][i];
        }
        return 1;
    }
    return 0;
}

void initialize (int N){
    n = N;
    for (i=1;i<=n;i++)
        t[i] = -1;
}

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