제출 #20747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20747		jjwdi0	게임 (IOI14_game)	C++11	100 / 100	543 ms	18736 KiB

game

#include "game.h"

int N, lim;
int A[1503][1503], cnt[2049];

int LCA(int u, int v) {
    u += lim, v += lim;
    while(u != v) u >>= 1, v >>= 1;
    return u;
}

void initialize(int n) {
    N = n;
    for(lim=1; lim<N; lim<<=1);
    for(int i=0; i<N; i++) for(int j=i+1; j<N; j++) {
        A[i][j] = A[j][i] = LCA(i, j);
        cnt[A[i][j]]++;
    }
}

int hasEdge(int u, int v) {
    return --cnt[A[u][v]] ? 0 : 1;
}

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