제출 #301475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301475		12tqian	슈퍼트리 잇기 (IOI20_supertrees)	C++14	96 / 100	263 ms	22264 KiB

supertrees

#ifdef LOCAL
#else
#include "supertrees.h"
#endif
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }
#ifdef LOCAL
bool build(vector<vector<int>> p) {
    return true;
}
#else
#endif
int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> res(n, vector<int>(n, 0));
    vector<bool> vis(n);
    auto ae = [&](int u, int v) {
        res[u][v] = 1;
        res[v][u] = 1;
    };
    auto make_cycle = [&](vector<int>& v) {
        for (int i = 0; i < v.size(); i++) {
            ae(v[i], v[(i + 1) % v.size()]);
        }
    };
    auto make_triple = [&](vector<int>& v) {
        make_cycle(v);
        ae(v[0], v[1]);
    };
    auto make_chain = [&](vector<int>& v) {
        for (int i = 0; i < v.size() - 1; i++) {
            ae(v[i], v[i + 1]);
        }
    };
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        vector<int> comp;
        function<void(int)> dfs_comp = [&](int src) {
            vis[src] = true;
            comp.push_back(src);
            for (int nxt = 0; nxt < n; nxt++) {
                if (p[src][nxt] == 0 || vis[nxt]) continue;
                dfs_comp(nxt);
            }
        };
        dfs_comp(i);
        int sz = comp.size();
        vector<int> overall(4);
        vector<int> one;
        vector<int> other;
        for (int x: comp) {
            vector<int> cnt(4);
            for (int y: comp) {
                if (x == y) continue;
                cnt[p[x][y]]++;
                overall[p[x][y]]++;
            }
            if (cnt[0]) {
                return 0;
            }
            if (cnt[1] == 0) {
                other.push_back(x);
            } else {
                one.push_back(x);
            }
        }
        if (overall[0] || overall[2] && overall[3]) {
            return 0;
        }
        if (overall[2] == 0 && overall[3] == 0) {
            vector<int> big;
            for (int x: one) big.push_back(x);
            for (int x: other) big.push_back(x);
            make_chain(big);
            continue;
        }
        vector<vector<int>> chains;
        for (int x: one) {
            bool done = false;
            for(auto& y: chains) {
                bool ok = false;
                for (int z: y) {
                    if (p[x][z] != 1) {
                        ok = true;
                        break;
                    }
                }
                if (ok == false) {
                    y.push_back(x);
                    done = true;
                    break;
                }
            }
            if (done == false) {
                chains.push_back(vector<int>(0));
                chains.back().push_back(x);
            }
        }
        for (auto& c: chains) {
            for (int x: c) {
                for (int y: c) {
                    if (p[x][y] != 1) {
                        return 0;
                    }
                }
            }
        }
        for (int j = 0; j < chains.size(); j++) {
            for (int k = j + 1; k < chains.size(); k++) {
                for (int x: chains[j]) {
                    for (int y: chains[k]) {
                        if (p[x][y] == 1) {
                            return 0;
                        }
                    }
                }
            }
        }
        int cycle = chains.size() + other.size();
        if (overall[2]) {
            if (cycle < 3) {
                return 0;
            }
            for (auto x: chains) {
                other.push_back(x[0]);
                make_chain(x);
            }
            make_cycle(other);
        } else if (overall[3]) {
            if (cycle < 4) {
                return 0;
            }
            for (auto x: chains) {
                other.push_back(x[0]);
                make_chain(other);
            }
            make_triple(other);
        } else {
            vector<int> big;
            for (int x: one) big.push_back(x);
            for (int x: other) big.push_back(x);
            make_chain(big);
        }
    }
    build(res);
    return 1;
}
#ifdef LOCAL
int main() {
    freopen("file.in", "r", stdin);
    int n; cin >> n;
    vector<vector<int>> p(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
        }
    }
    cout << construct(p) << '\n';
    return 0;
}
#else
#endif

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

supertrees.cpp: In lambda function:
supertrees.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
supertrees.cpp: In lambda function:
supertrees.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int i = 0; i < v.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |         if (overall[0] || overall[2] && overall[3]) {
supertrees.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for (int j = 0; j < chains.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
supertrees.cpp:122:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for (int k = j + 1; k < chains.size(); k++) {
      |                                 ~~^~~~~~~~~~~~~~~
supertrees.cpp:60:13: warning: unused variable 'sz' [-Wunused-variable]
   60 |         int sz = comp.size();
      |             ^~

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