답안 #301466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
301466 2020-09-18T01:31:17 Z 12tqian 슈퍼트리 잇기 (IOI20_supertrees) C++17
0 / 100
1 ms 256 KB
#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;
        }
        vector<int> le;
        vector<int> ri;
        for (int x: one) {
            bool ok = false;
            for (int y: le) {
                if (p[x][y] != 1) {
                    ri.push_back(x);
                    ok = true;
                    break;
                }
            }
            if (ok == false) {
                le.push_back(x);
            }
        }
        for (int x: le) {
            for (int y: le) {
                if (x == y) continue;
                if (p[x][y] != 1) {
                    return 0;
                }
            }
        }
        for (int x: ri) {
            for (int y: ri) {
                if (x == y) continue;
                if (p[x][y] != 1) {
                    return 0;
                }
            }
        }
        for (int x: le) {
            for (int y: ri) {
                if (overall[2] && p[x][y] != 2) {
                    return 0;
                }
                if (overall[3] && p[x][y] != 3) {
                    return 0;
                }
            }
        }
        int cycle = (le.size() ? 1 : 0) + (ri.size() ? 1 : 0) + other.size();
        if (overall[2]) {
            if (cycle < 3) {
                return 0;
            }
            if (le.size() == 0 && ri.size() == 0) {
                make_cycle(other);
                for (int j = 0; j < other.size(); j++) {
                    ae(other[j], other[(j + 1) % other.size()]);
                }
            } else if (le.size() == 0) {
                other.push_back(ri[0]);
                make_cycle(other);
                make_chain(ri);
            } else if (ri.size() == 0) {
                other.push_back(le[0]);
                make_cycle(other);
                make_chain(le);
            } else {
                other.push_back(le[0]);
                other.push_back(ri[0]);
                make_cycle(other);
                make_chain(le);
                make_chain(ri);
            }
        } else if (overall[3]) {
            if (cycle < 4) {
                return 0;
            }
            if (le.size() == 0 && ri.size() == 0) {
                make_triple(other);
                for (int j = 0; j < other.size(); j++) {
                    ae(other[j], other[(j + 1) % other.size()]);
                }
            } else if (le.size() == 0) {
                other.push_back(ri[0]);
                make_triple(other);
                make_chain(ri);
            } else if (ri.size() == 0) {
                other.push_back(le[0]);
                make_triple(other);
                make_chain(le);
            } else {
                other.push_back(le[0]);
                other.push_back(ri[0]);
                make_triple(other);
                make_chain(le);
                make_chain(ri);
            }
        } else {
            vector<int> big;
            for (int x: one) big.push_back(x);
            for (int x: other) big.push_back(x);
            make_chain(big);
        }
    }
    for (auto row: res) cout << row << '\n';
    build(res);
    return 1;
}
#ifdef LOCAL
int main() {
    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];
        }
    }
    construct(p);
    return 0;
}
#else
#endif

Compilation message

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:131:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |                 for (int j = 0; j < other.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~
supertrees.cpp:155:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |                 for (int j = 0; j < other.size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~
supertrees.cpp:60:13: warning: unused variable 'sz' [-Wunused-variable]
   60 |         int sz = comp.size();
      |             ^~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 256 KB secret mismatch
2 Halted 0 ms 0 KB -