제출 #666868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666868		YENGOYAN	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	203 ms	22092 KiB

supertrees

#include "supertrees.h"
#include <vector>

using namespace std;

vector<int> par, sizes;

int get(int u){
    if(par[u] == u) return u;
    return par[u] = get(par[u]);
}

void union_sets(int u, int v){
    int a = get(u), b = get(v);
    if(a == b) return;
    if(sizes[a] < sizes[b]) swap(a, b);
    par[b] = a;
    sizes[a] += sizes[b];
}

vector<int> comp;

void dfs(int u, vector<bool> &vis, vector<vector<int>> &gp){
    vis[u] = 1;
    comp.push_back(u);
    for(int &v : gp[u]){
        if(!vis[v]){
            dfs(v, vis, gp);
        }
    }
}

bool isok = true;

vector<vector<int>> sol(vector<vector<int>> p){
    isok = true;
    int n = p.size();
    vector<vector<int>> gp(n,  vector<int> (n));
    vector<vector<int>> graph(n);
    par = sizes = vector<int> (n);
	for(int i = 0; i < n;i++) par[i] = i, sizes[i] = 1;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(p[i][j] == 2){
                union_sets(i, j);
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int u = get(i), v = get(j);
            if(p[i][j] == 2 && u != v) isok = false;
            if(p[i][j] != 2 && u == v) isok = false;
        }
    }
    vector<bool> vis(n);
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            comp.clear();
            dfs(i, vis, graph);
            if(comp.size() == 2) isok = false;
            if(comp.size() == 1 && p[i][i] != 1)  isok = false;
            for(int i = 1; i < comp.size(); i++){
                gp[comp[i]][comp[i - 1]] = gp[comp[i - 1]][comp[i]] = 1;
            }
            if(comp.size() > 1) gp[comp[0]][comp.back()] = gp[comp.back()][comp[0]] = 1;
        }
    }
    return gp;
}

int construct(vector<vector<int>> p) {

	int n = p.size();
	vector<vector<int>> gp(n, vector<int> (n));
	par = sizes = vector<int> (n);
	for(int i = 0; i < n;i++) par[i] = i, sizes[i] = 1;
    bool f = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(p[i][j] == 2) f = 1;
    if(f) {
        vector<vector<int>> res = sol(p);
        if(isok) build(res);
        else return 0;
        return 1;
    }
	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!p[i][j]) continue;
            int u = get(i), v = get(j);
            if(u != v) union_sets(u, v), gp[i][j] = gp[j][i] = 1;
        }
	}
	for(int i = 0; i < n;i++){
        for(int j = 0; j < n;j++){
            int u = get(i), v = get(j);
            if((u == v) != p[i][j]) return 0;
        }
	}
	build(gp);
	return 1;
}

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

supertrees.cpp: In function 'std::vector<std::vector<int> > sol(std::vector<std::vector<int> >)':
supertrees.cpp:65:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int i = 1; i < comp.size(); i++){
      |                            ~~^~~~~~~~~~~~~

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