제출 #397293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397293		ruadhan	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	307 ms	30644 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;

// void build(vector<vector<int>> b)
// {
//     for (auto r : b)
//     {
//         for (auto c : r)
//         cerr << c << " ";
//         cerr << '\n';
//     }
//     cerr << '\n';
// }

const int MX = 1005;
int N;
vector<int> adj[MX];

vector<int> component, vis(MX);
void dfs(int u)
{
    // cerr << "dfs on " << u << '\n';
    vis[u] = 1;
    component.push_back(u);
    for (int v : adj[u])
        if (!vis[v])
            dfs(v);
}

vector<int> tree[MX];
vector<int> vis2(MX), outside_cycle(MX);
vector<bool> in_tree(MX);
void dfs2(int u)
{
    // cerr << "doing dfs2 on " << u << '\n';
    vis2[u] = 1;
    outside_cycle.push_back(u);
    for (int v : tree[u])
        if (!vis2[v])
            dfs2(v);
}

int construct(vector<vector<int>> p)
{
    N = p.size();
    // cerr << "N = " << N << '\n';
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            if (p[i][j] == 3)
                return 0;
            if (p[i][j] > 0)
            {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // cerr << "created adjacency list " << '\n';

    vector<vector<int>> ans(N, vector<int>(N));

    for (int node = 0; node < N; node++)
    {
        // cerr << "N = " << N << '\n';
        // cerr << "node = " << node << '\n';

        if (!vis[node])
        {
            component.clear();
            dfs(node);

            int n = sz(component);
            // cerr << "size of component = n = " << n << '\n';
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    int u = component[i], v = component[j];
                    // cerr << "i = " << i << ", j = " << j << '\n';
                    if (p[u][v] == 0)
                        return 0;
                    if (p[u][v] == 1)
                    {
                        tree[u].push_back(v);
                        tree[v].push_back(u);
                    }
                }
            }
            // cerr << "tree counting finished\n";
            vector<int> cycle;
            for (int idx : component)
                if (!vis2[idx])
                {
                    outside_cycle.clear();
                    dfs2(idx);
                    // cerr << "finished doing dfs2\n";
                    for (int u : outside_cycle)
                        in_tree[u] = true;
                    for (int u : outside_cycle)
                    {
                        for (int v : component)
                        {
                            if (in_tree[v] && p[u][v] != 1)
                            {
                                // cerr << "returning 0" << '\n';
                                return 0;
                            }
                            if (!in_tree[v] && p[u][v] != 2)
                            {
                                // cerr << "returning 0" << '\n';
                                return 0;
                            }
                        }
                    }
                    for (int i = 0; i < sz(outside_cycle) - 1; i++)
                    {
                        int u = outside_cycle[i], v = outside_cycle[i + 1];
                        ans[u][v] = ans[v][u] = 1;
                    }
                    cycle.push_back(outside_cycle[0]);
                    for (int u : outside_cycle)
                        in_tree[u] = false;
                }
            // cerr << "sz(cycle) = " << sz(cycle) << '\n';
            if (sz(cycle) == 2)
                return 0;
            if (sz(cycle) > 2)
            {
                for (int i = 0; i < sz(cycle); i++)
                {
                    int u = cycle[i], v = cycle[(i + 1 == sz(cycle) ? 0 : i + 1)];
                    ans[u][v] = ans[v][u] = 1;
                }
            }
        }
    }
    build(ans);
    return 1;
}

// int main()
// {
//     int n;
//     cin >> n;
//     vector<vector<int>> in(n, vector<int>(n));
//     for (auto &r : in)
//     {
//         for (auto &c : r)
//             cin >> c;
//     }
//     for (auto x : in)
//     {
//         for (auto y : x)
//             // cerr << y << " ";
//         // cerr << '\n';
//     }
//     construct(in);
//     return 0;
// }

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