oj.uz

답안 #510480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
510480 2022-01-15T01:27:42 Z tabr 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
 1 ms 296 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

void build(vector<vector<int>>);

int construct(vector<vector<int>> p) {
    int n = (int) p.size();
    vector<int> a(n);
    iota(a.begin(), a.end(), 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] == 1) {
                a[j] = min(a[j], i);
            }
        }
    }
    vector<vector<int>> res(n, vector<int>(n));
    vector<vector<int>> c(n);
    for (int i = 0; i < n; i++) {
        if (a[i] < i) {
            res[a[i]][i] = res[i][a[i]] = 1;
        }
        c[a[i]].emplace_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] != p[a[i]][a[j]]) {
                return 0;
            }
        }
    }
    vector<int> b(n);
    iota(b.begin(), b.end(), 0);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == i && a[j] == j && p[i][j] == 2) {
                b[j] = min(b[j], i);
            }
        }
    }
    c = vector<vector<int>>(n);
    for (int i = 0; i < n; i++) {
        if (a[i] == i) {
            c[b[i]].emplace_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        int sz = (int) c[i].size();
        if (sz == 1 || sz == 2) {
            return 0;
        }
        for (int j = 0; j < sz; j++) {
            p[c[i][j]][c[i][(j + 1) % sz]] = p[c[i][(j + 1) % sz]][c[i][j]] = 1;
        }
    }
    build(res);
    return 1;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 296 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -