oj.uz

답안 #902259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902259 2024-01-10T07:40:15 Z Ghulam_Junaid 게임 (IOI14_game) C++17
0 / 100
 1 ms 2648 KB 
#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

const int MXN = 1505;
int n, par[MXN], seen[MXN][MXN];
vector<int> S[MXN];

int root(int v){
    return ((par[v] == -1) ? (v) : (par[v] = root(par[v])));
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return;

    if (S[u].size() > S[v].size())
        swap(u, v);

    par[u] = v;
    for (int x : S[u])
        S[v].push_back(x);
    S[u].clear();
}

void initialize(int N){
    n = N;
    for (int i=0; i<n; i++){
        S[i].push_back(i);
        par[i] = -1;
    }
}
int hasEdge(int u, int v){
    seen[u][v] = 1;

    u = root(u), v = root(v);
    if (u == v) return 0;

    int cnt = 0;
    for (int x : S[u])
        for (int y : S[v])
            cnt += seen[x][y];

    if (cnt == (S[u].size() * S[v].size()) ){
        merge(u, v);
        return 1;
    }

    return 0;
}

// int main(){
//     int n;
//     cin >> n;

//     initialize(n);
//     for (int i=0; i<(n * (n - 1)) / 2; i++){
//         int u, v;
//         cin >> u >> v;

//         cout << hasEdge(u, v) << endl;
//     }
// }

Compilation message

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if (cnt == (S[u].size() * S[v].size()) ){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Incorrect 0 ms 2408 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2404 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2532 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2408 KB Output is correct
6 Correct 1 ms 2400 KB Output is correct
7 Incorrect 1 ms 2400 KB Output isn't correct
8 Halted 0 ms 0 KB -