oj.uz

답안 #103762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
103762 2019-04-02T12:59:30 Z Osama_Alkhodairy 게임 (IOI14_game) C++17
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
//#include "grader.cpp"
using namespace std;

const int N = 1501;

int n, dsu[N], ok[N][N], sz[N];
vector <vector <int> > cnt;

int find(int x){
    if(dsu[x] == x) return x;
    return dsu[x] = find(dsu[x]);
}
void initialize(int nn){
    n = nn;
    cnt.assign(n, vector <int>(n, 0));
    for(int i = 0 ; i < n ; i++)
        dsu[i] = i;
    for(int i = 0 ; i < n ; i++){
        for(int j = i + 1 ; j < n ; j++){
            ok[i][j] = ok[j][i] = 1;
        }
    }
}
void merge(int x, int y){
    sz[x] += sz[y];
    dsu[y] = x;
    for(int i = 0 ; i < n ; i++)
        cnt[x][i] += cnt[y][i];
    for(int i = 0 ; i < n ; i++){
        if(find(i) == i && i != x){
            ok[i][x] = ok[x][i] = sz[x] * sz[i];
        }
    }
    for(int i = 0 ; i < n ; i++){
        int r = find(i);
        if(r == x) continue;
        ok[x][r] -= cnt[x][i];
        ok[r][x] -= cnt[x][i];
    }
}
int hasEdge(int u, int v){
    int x = find(u);
    int y = find(v);
    if(x == y) return 1;
    ok[x][y]--;
    ok[y][x]--;
    cnt[x][y]++;
    cnt[y][x]++;
    if(ok[x][y] == 0){
        merge(x, y);
        return 1;
    }
    return 0;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -