제출 #927401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927401		VMaksimoski008	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	154 ms	22040 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
 
struct DSU {
    int n, comp;
    vector<int> par, size;
 
    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }
 
    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }
 
    bool uni(int u, int v) {
        u = get(u), v = get(v);
 
        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);
 
        size[u] += size[v];
        par[v] = u;
        comp--;
 
        return true;
    }
 
    int getComp() { return comp; }
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
    bool isLeader(int u) { return get(u) == u; }
};

vector<vector<int> > graph;
vector<bool> vis;
vector<int> G;

void dfs(int u) {
    vis[u] = 1;
    G.push_back(u);

    for(int &v : graph[u]) {
        if(vis[v]) continue;
        dfs(v);
    }
}
 
int construct(vector<vector<int> > p) {
    int n = p.size();
    vector<int> cnt(4);
    vector<vector<int> > B(n, vector<int>(n, 0));
    graph.resize(n);
    vis.resize(n);

    DSU dsu; dsu.config(n);

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cnt[p[i][j]]++;

    if(cnt[1] == n && cnt[1] + cnt[0] == n*n) {
        build(B);
        return 1;
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i == j) continue;
            if(p[i][j] == 3) return 0;
            if(dsu.uni(i, j))
                B[i][j] = B[j][i] = 1;
        }
    }

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(i != j && dsu.sameSet(i, j) && p[i][j] == 0) return 0;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i != j && p[i][j] == 2 && dsu.isLeader(i) && dsu.isLeader(j)) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }

    for(int i=0; i<n; i++) {
        if(vis[i]) continue;

        G.clear();
        dfs(i);

        if(G.size() == 2) return 0;
        if(G.size() == 1) continue;

        for(int i=0; i<G.size()-1; i++)
            for(int j=i+1; j<G.size(); j++)
                if(p[i][j] != 2) return 0;

        G.push_back(G[0]);
        for(int i=0; i<G.size()-1; i++)
            B[G[i]][G[i+1]] = B[G[i+1]][G[i]] = 1;
    }

    build(B);
    return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i=0; i<G.size()-1; i++)
      |                      ~^~~~~~~~~~~
supertrees.cpp:105:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for(int j=i+1; j<G.size(); j++)
      |                            ~^~~~~~~~~
supertrees.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int i=0; i<G.size()-1; i++)
      |                      ~^~~~~~~~~~~

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