제출 #362543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362543		valerikk	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	275 ms	27504 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std; 

const int N = 1007;

vector<int> g[N];
bool vis[N];
int cmp[N];
vector<int> comp;
int par[N];

int find_par(int v) {
    return par[v] == v ? v : par[v] = find_par(par[v]);
}

bool unite(int v, int u) {
    v = find_par(v);
    u = find_par(u);
    par[v] = u;
    return v != u;
}

void dfs(int v, int st) {
    vis[v] = true;
    cmp[v] = st;
    comp.push_back(v);
    for (int u : g[v]) {
        if (!vis[u]) dfs(u, st);
    }
}


int construct(vector<vector<int>> p) {
    int n = p.size();
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < n; i++) {
        if (p[i][i] != 1) return 0;
        for (int j = 0; j < i; j++) {
            if (p[i][j] != p[j][i]) return 0;
            if (p[i][j] == 3) return 0;
            if (p[i][j] > 0) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    vector<vector<int>> b(n, vector<int>(n, 0));
    auto add_edge = [&](int v, int u) {
        b[v][u] = b[u][v] = 1;
    };
    for (int i = 0; i < n; i++) {
        vis[i] = false;
        cmp[i] = -1;
    }
    for (int st = 0; st < n; st++) {
        if (!vis[st]) {
            comp = {};
            dfs(st, st);
            bool ok = true;
            for (int v : comp) {
                for (int u : comp) ok &= p[v][u] > 0;
                for (int i = 0; i < n; i++) {
                    if (cmp[i] != st) ok &= p[v][i] == 0;
                }
            }
            if (!ok) return 0;
            bool has = false;
            for (int v : comp) {
                for (int u : comp) has |= p[v][u] == 2;
            }
            if (has) {
                for (int i = 0; i < n; i++) par[i] = i;
                for (int v : comp) {
                    for (int u : comp) {
                        if (p[v][u] == 1) unite(v, u);
                    }
                }
                for (int v : comp) {
                    for (int u : comp) {
                        if (find_par(v) == find_par(u) && p[v][u] == 2) return 0;
                        if (find_par(v) != find_par(u) && p[v][u] == 1) return 0;
                    }
                }
                for (int v : comp) find_par(v);
                vector<int> arr;
                for (int v : comp) arr.push_back(find_par(v));
                sort(arr.begin(), arr.end());
                arr.erase(unique(arr.begin(), arr.end()), arr.end());
                if (arr.size() < 3) return 0;
                vector<vector<int>> arrs(arr.size());
                for (int v : comp) {
                    arrs[lower_bound(arr.begin(), arr.end(), find_par(v)) - arr.begin()].push_back(v);
                }
                for (int i = 0; i < arr.size(); i++) {
                    for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
                }
                for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
            } else {
                for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
            }
        }
    }
    build(b);
    return 1;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:95:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for (int i = 0; i < arr.size(); i++) {
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:96:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                     for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
      |                                     ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:98:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
      |                                 ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4