제출 #835953

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

supertrees

// I can do all things through Christ who strengthens me
// Philippians 4:13

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)

template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 1005;

int n;
vector<vi> g;
vector<vi> ans;
bool vis[MAXN];

bool incyc[MAXN];
bool solve(vi comp) {
    if (SZ(comp) == 1) {
        return 1;
    }
    vi cyc, line;
    for (int i : comp) {
        bool all2 = 1;
        for (int j : comp) {
            if (i == j) {
                continue;
            }
            if (g[i][j] != 2) {
                all2 = 0;
                break;
            }
        }
        if (all2) {
            cyc.pb(i);
            incyc[i] = 1;
        } else {
            line.pb(i);
        }
    }
    for (int i : line) {
        for (int j : comp) {
            if (j == i) {
                continue;
            }
            if (incyc[j]) {
                if (g[i][j] != 2) {
                    return 0;
                }
            } else {
                if (g[i][j] != 1) {
                    return 0;
                }
            }
        }
    }
    if (SZ(cyc) == 1) {
        assert(0);
        return 0;
    }
    if (line.empty()) {
        if (SZ(cyc) == 2) {
            return 0;
        }
        REP (i, 0, SZ(cyc)) {
            ans[cyc[i]][cyc[(i + 1) % SZ(cyc)]] = 1;
            ans[cyc[(i + 1) % SZ(cyc)]][cyc[i]] = 1;
        }
        return 1;
    }
    REP (i, 0, SZ(line) - 1) {
        ans[line[i]][line[i + 1]] = 1;
        ans[line[i + 1]][line[i]] = 1;
    }
    if (!cyc.empty()) {
        REP (i, 0, SZ(cyc) - 1) {
            ans[cyc[i]][cyc[i + 1]] = 1;
            ans[cyc[i + 1]][cyc[i]] = 1;
        }
        ans[line[0]][cyc[0]] = 1;
        ans[cyc[0]][line[0]] = 1;
        ans[line[0]][cyc.back()] = 1;
        ans[cyc.back()][line[0]] = 1;
    }
    return 1;
}

int construct(vector<vi> p) {
    n = SZ(p);
    ans = vector<vi>(n, vi(n, 0));
    g = p;
    REP (i, 0, n) {
        REP (j, 0, n) {
            if (g[i][j] == 3) {
                return 0;
            }
        }
    }
    REP (i, 0, n) {
        if (vis[i]) {
            continue;
        }
        vi comp;
        REP (j, 0, n) {
            if (g[i][j]) {
                comp.pb(j);
            }
        }
        for (int j : comp) {
            vis[j] = 1;
            REP (k, 0, n) {
                if ((g[j][k] > 0) != (g[i][k] > 0)) {
                    return 0;
                }
            }
        }
        if (!solve(comp)) {
            return 0;
        }
    }
    build(ans);
    return 1;
}

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