제출 #526947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526947		Olympia	슈퍼트리 잇기 (IOI20_supertrees)	C++17	40 / 100	214 ms	24176 KiB

supertrees

#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include "supertrees.h"

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")

using namespace std;

class DisjointSetUnion {
protected:
    vector<int> parent;
    vector<int> compSize;
    const int n;
    int connectedComponents;
public:
    int getConnectedComponents() const {
        return connectedComponents;
    }

public:
    DisjointSetUnion(int sz) : n(sz), connectedComponents(sz) {
        parent.resize(sz), compSize.resize(sz);
        for (int i = 0; i < n; i++) {
            parent[i] = i, compSize[i] = 1;
        }
    }

    int find_head(int x) const {
        int cur = x;
        while (cur != parent[cur]) {
            cur = parent[cur];
        }
        return cur;
    }

    void join(int x, int y) {
        x = find_head(x);
        y = find_head(y);
        if (x == y) {
            return;
        }
        if (compSize[x] > compSize[y]) {
            swap(x, y);
            //ensures that compSize[x1] <= compSize[y1]
        }
        parent[x] = y;
        compSize[y] += compSize[x];
        connectedComponents--;
    }

    bool comp(int x, int y) {
        return (find_head(x) == find_head(y));
    }
};


/*
void build (vector<vector<int>> grid) {
    for (int i = 0; i < grid.size(); i++) {
        for (int j: grid[i]) {
            cout << j << ' ';
        }
        cout << '\n';
    }
}
*/


int construct (vector<vector<int>> grid) {
    vector<vector<int>> ans(grid.size());
    for (int i = 0; i < grid.size(); i++) {
        ans[i].assign(grid[0].size(), 0);
    }
    set<int> s;
    map<int,int> cnt;
    DisjointSetUnion disjointSetUnion(grid.size());
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid.size(); j++) {
            s.insert(grid[i][j]);
            cnt[grid[i][j]]++;
            if (grid[i][j] != 0) {
                disjointSetUnion.join(i, j);
            }
        }
    }
    if (s.count(1) && s.size() == 1) {
        for (int i = 1; i < grid.size(); i++) {
            ans[i][0] = ans[0][i] = 1;
        }
        build(ans);
        return 1;
    }
    map<int,vector<int>> myMap;
    for (int i = 0; i < grid.size(); i++) {
        myMap[disjointSetUnion.find_head(i)].push_back(i);
    }
    if (cnt[2] == 0 && cnt[3] == 0) {
        for (auto& p: myMap) {
            vector<int> v = p.second;
            for (int i = 1; i < (int)v.size(); i++) {
                ans[v[i]][v[0]] = 1;
                ans[v[0]][v[i]] = 1;
            }
            for (int x: v) {
                for (int y: v) {
                    if (grid[x][y] != 1) return false;
                }
            }
        }
        build(ans);
        return 1;
    }
    if (cnt[0] >= 0 && cnt[1] == (int)grid.size() && cnt[2] >= 0 && cnt[3] == 0) {
        for (auto& p: myMap) {
            vector<int> v = p.second;
            if (v.size() == 2) {
                return 0;
            }
            if (v.size() <= 1) {
                continue;
            }
            for (int i = 1; i < (int)v.size(); i++) {
                ans[v[i]][v[i - 1]] = 1;
                ans[v[i - 1]][v[i]] = 1;
            }
            ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1;
            for (int x: v) {
                for (int y: v) {
                    if (grid[x][y] == 0) {
                        return 0;
                    }
                }
            }
        }
        build(ans);
        return 1;
    }
    if (cnt[0] >= 0 && cnt[1] > 0 && cnt[2] > 0 && cnt[3] == 0) {
        //cout << "YES\n";
        for (auto& p: myMap) {
            DisjointSetUnion dsu(grid.size());
            map<int,vector<int>> m;
            for (int x: p.second) {
                for (int y: p.second) {
                    if (grid[x][y] == 1) {
                        dsu.join(x, y);
                    }
                }
            }
            for (int i = 0; i < grid.size(); i++) {
                m[dsu.find_head(i)].push_back(i);
            }
            vector<int> vec;
            for (auto& q: m) {
                vec.push_back(q.first);
            }
            //cout << "GET " << vec.size() << '\n';
            for (int i = 1; i < vec.size(); i++) {
                ans[vec[i]][vec[i - 1]] = ans[vec[i - 1]][vec[i]] = 1;
            }
            for (auto& q: m) {
                vector<int> v = q.second;
                for (int i = 1; i < (int)v.size(); i++) {
                    ans[v[i]][v[0]] = 1;
                    ans[v[0]][v[i]] = 1;
                }
                for (int x: v) {
                    //cout << x << " ? ";
                }
                //cout << '\n';
                for (int x: v) {
                    for (int y: v) {
                        //cout << x << " ? " << y << '\n';
                        if (grid[x][y] != 1) return false;
                    }
                }
            }

        }
        build(ans);
        return 1;
    }

}

/*
int main () {
    const int N = 7;
    vector<vector<int>> grid(N);
    for (int i = 0; i < N; i++) {
        grid[i].assign(N, 1);
    }
    grid[1][2]++, grid[2][1]++;
    grid[2][4]++, grid[4][2]++;
    grid[1][3]++, grid[3][1]++;
    grid[1][4]++, grid[4][1]++;
    grid[3][4]++, grid[4][3]++;
    grid[3][2]++, grid[2][3]++;
    grid[0][5]++, grid[5][0]++;
    grid[0][6]++, grid[6][0]++;
    grid[0][4]++, grid[4][0]++;
    grid[3][5]++, grid[5][3]++;
    grid[5][2]++, grid[2][5]++;
    grid[1][5]++, grid[5][1]++;
    grid[2][6]++, grid[6][2]++;
    grid[3][6]++, grid[6][3]++;
    grid[3][0]++, grid[0][3]++;
    grid[1][6]++, grid[6][1]++;
    grid[0][2]++, grid[2][0]++;


    construct(grid);
}
*/

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

supertrees.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O3")
      | 
supertrees.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("Ofast")
      | 
supertrees.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("unroll-loops")
      | 
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int j = 0; j < grid.size(); j++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 1; i < grid.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < grid.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:163:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |             for (int i = 0; i < grid.size(); i++) {
      |                             ~~^~~~~~~~~~~~~
supertrees.cpp:171:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |             for (int i = 1; i < vec.size(); i++) {
      |                             ~~^~~~~~~~~~~~
supertrees.cpp:180:26: warning: unused variable 'x' [-Wunused-variable]
  180 |                 for (int x: v) {
      |                          ^
supertrees.cpp:83:40: warning: control reaches end of non-void function [-Wreturn-type]
   83 |     vector<vector<int>> ans(grid.size());
      |                                        ^

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