제출 #418860

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418860		usachevd0	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	286 ms	26852 KiB

supertrees

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "supertrees.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream operator << (ostream& stream, const vector<T>& v) {
    for (auto& e : v)
        stream << e << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}


namespace sol {
    const int maxN = 1003;
    int n;
    int p[maxN][maxN];
    int comps1, comps2;
    int comp1[maxN], comp2[maxN];
    int topv[maxN];
    vector<int> circle[maxN];

    void dfs1(int v) {
        comp1[v] = comps1;
        for (int u = 0; u < n; ++u)
            if (comp1[u] == -1 && p[v][u] >= 1)
                dfs1(u);
    }
    void dfs2(int v) {
        comp2[v] = comps2;
        for (int u = 0; u < n; ++u)
            if (comp2[u] == -1 && p[v][u] == 1)
                dfs2(u);
    }
}


void build(vector<vector<int>> adj);
int construct(vector<vector<int>> _p) {
    using namespace sol;
    n = _p.size();
    for (int u = 0; u < n; ++u)
        for (int v = 0; v < n; ++v) {
            p[u][v] = _p[u][v];
            if (p[u][v] == 3) {
                return 0;
            }
        }
    memset(comp1, 255, sizeof comp1);
    comps1 = 0;
    for (int v = 0; v < n; ++v) {
        if (comp1[v] != -1) continue;
        dfs1(v);
        ++comps1;
    }
    for (int u = 0; u < n; ++u)
        for (int v = 0; v < n; ++v)
            if (comp1[u] == comp1[v] && p[u][v] == 0)
                return 0;
    memset(comp2, 255, sizeof comp2);
    comps2 = 0;
    for (int v = 0; v < n; ++v) {
        if (comp2[v] != -1) continue;
        dfs2(v);
        ++comps2;
    }
    for (int u = 0; u < n; ++u)
        for (int v = 0; v < n; ++v)
            if (comp2[u] == comp2[v] && p[u][v] != 1)
                return 0;
    memset(topv, 255, sizeof topv);
    vector<vector<int>> adj(n, vector<int>(n, 0));
    auto addEdge = [&](int a, int b) {
        adj[a][b] = adj[b][a] = 1;
    };
    for (int v = 0; v < n; ++v) {
        int c2 = comp2[v];
        if (topv[c2] == -1)
            topv[c2] = v;
        else {
            addEdge(topv[c2], v);
        }
    }
    for (int c2 = 0; c2 < comps2; ++c2) {
        int v = topv[c2];
        int c1 = comp1[v];
        circle[c1].push_back(v);
    }
    for (int c1 = 0; c1 < comps1; ++c1) {
        if (circle[c1].size() == 1) continue;
        if (circle[c1].size() == 2) return 0;
        for (int i = 0; i < circle[c1].size(); ++i) {
            addEdge(circle[c1][i], circle[c1][(i + 1) % circle[c1].size()]);
        }
    }
    build(adj);
    return 1;
}

#ifdef LOCAL
 int n;
 std::vector<std::vector<int>> p;
 std::vector<std::vector<int>> b;
 bool called = false;

 void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}

int main() {
    freopen("in", "r", stdin);
    
    assert(scanf("%d", &n) == 1);
    
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i].resize(n);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(p);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}

#endif

/*
#ifdef LOCAL
int32_t main() {
    #ifdef LOCAL
        freopen("in", "r", stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    
    
    return 0;
}
#endif*/

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:134:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for (int i = 0; i < circle[c1].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~

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