제출 #301517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301517		Gilgamesh	슈퍼트리 잇기 (IOI20_supertrees)	C++17	75 / 100	268 ms	22296 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <set>
const int mxN = 1000;

int parent[mxN];
int rnk[mxN];

int find(int x) 
{ 
    if(parent[x] == -1)
        parent[x] = x;
    if (parent[x] != x) { 
        parent[x] = find(parent[x]); 
    }
    return parent[x]; 
}
bool merge(int x, int y) 
{ 
    int xRoot = find(x), yRoot = find(y); 
    if (xRoot == yRoot) 
        return false; 
    if (rnk[xRoot] < rnk[yRoot]) 
        parent[xRoot] = yRoot; 
    else if (rnk[yRoot] < rnk[xRoot]) 
        parent[yRoot] = xRoot; 
    else 
    { 
        parent[yRoot] = xRoot; 
        rnk[xRoot] = rnk[xRoot] + 1; 
    } 
    return true;
} 


int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    std::vector<std::vector<int>> answer;
    for (int i = 0; i < n; i++) {
        std::vector<int> row;
        row.resize(n);
        answer.push_back(row);
    }
    bool zero = false, one = false, two = false, three = false;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(p[i][j] == 0) zero = true;
            else if(p[i][j] == 1) one = true;
            else if(p[i][j] == 2) two = true;
            else three = true;
        }
    }
    for(int i = 0; i < n; ++i){
        parent[i] = i;
    }
    if(!one && !three){
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(!p[i][j] && find(i) == find(j)){
                    return 0;
                }
                if(p[i][j]) merge(i, j);
            }
        }
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(!p[i][j] && find(i) == find(j)) return 0;
            }
        }
        std::vector<int> sets[n];
        for(int i = 0; i < n; ++i){
            int rep = find(i);
            sets[rep].emplace_back(i);
        }
        for(int i = 0; i < n; ++i){
            int sz = sets[i].size();
            if(sz == 2) return 0;
            for(int j = 0; j < sz - 1; ++j){
                answer[sets[i][j]][sets[i][j + 1]] = 1;
                answer[sets[i][j + 1]][sets[i][j]] = 1;
            }
            if(sz > 1){
                answer[sets[i][0]][sets[i][sz-1]] = 1;
                answer[sets[i][sz-1]][sets[i][0]] = 1;
            }
        }
    }
    else if(!two && !three){
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(!p[i][j] && find(i) == find(j)){
                    return 0;
                }
                if(p[i][j]) merge(i, j);
            }
        }
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(!p[i][j] && find(i) == find(j)) return 0;
            }
        }
        for(int i = 0; i < n; ++i){
            int rep = find(i);
            if(rep == i) continue;
            answer[rep][i] = 1;
            answer[i][rep] = 1;
        }
    }
    else if(!three){
        for(int i = 0; i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                if(p[i][j]) merge(i, j);
            }
        }
        std::set<int> sets[mxN];
        for(int i = 0; i < n; ++i){
            int rep = find(i);
            sets[rep].insert(i);
        }
        for(int rep = 0; rep < n; ++rep){
            if(sets[rep].size() < 2) continue;
            std::vector<int> circle;
            std::set<int> remove;
            for(int i : sets[rep]){
                if(remove.find(i) != remove.end()) continue;
                for(int j = 0; j < n; ++j){
                    if(j == i) continue;
                    if(p[i][j] == 1){
                        answer[i][j] = 1;
                        answer[j][i] = 1;
                        remove.insert(j);
                    }
                }
                circle.emplace_back(i);
            }
            int sz = circle.size();
            for(int i = 0; i < sz - 1; ++i){
                answer[circle[i]][circle[i + 1]] = 1;
                answer[circle[i + 1]][circle[i]] = 1;
            }
            if(sz > 1){
                answer[circle[0]][circle[sz-1]] = 1;
                answer[circle[sz-1]][circle[0]] = 1;
            }
        }
    }
    build(answer);
    return 1;
}

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:44:10: warning: variable 'zero' set but not used [-Wunused-but-set-variable]
   44 |     bool zero = false, one = false, two = false, three = false;
      |          ^~~~

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