Submission #1202312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202312		onbert	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	122 ms	26172 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int n;
vector<vector<int>> G;
bool vis[maxn];

bool inloop[maxn];
int belong[maxn];
vector<int> nodes;
void dfs(int u) {
    vis[u] = true;
    nodes.push_back(u);
    for (int v=0;v<n;v++) if (G[u][v] && !vis[v]) dfs(v);
}

void dfs2(int u, int rt) {
    vis[u] = true, belong[u] = rt;
    for (int v=0;v<n;v++) if (G[u][v] == 1 && !vis[v]) dfs2(v, rt);
}

int construct(vector<vector<int>> p) {
	n = p.size();
    G = p;
	vector<vector<int>> ans(n, vector<int>(n));

    for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (G[i][j] == 3) return 0;
    
    for (int i=0;i<n;i++) belong[i] = -1;
    for (int i=0;i<n;i++) if (!vis[i]) {
        nodes.clear();
        dfs(i);
        for (int u:nodes) for (int v:nodes) if (!G[u][v]) return 0;
        for (int u:nodes) vis[u] = false;
        vector<int> loop;
        for (int u:nodes) if (!vis[u]) {
            inloop[u] = true;
            loop.push_back(u);
            dfs2(u, u);
        }


        int sz = loop.size();
        if (sz == 2) return false;
        if (sz > 2) {
            for (int j=0;j<sz;j++) ans[loop[j]][loop[(j+1)%sz]] = ans[loop[(j+1)%sz]][loop[j]] = 1;
        }

        for (int u:nodes) if (!inloop[u]) {
            bool done = false;
            for (int v:nodes) if (inloop[v] && G[u][v] == 1) {
                if (done) return 0;
                done = true;
                ans[u][v] = ans[v][u] = 1;
                belong[u] = v;
            }
        }
        for (int u:nodes) if (!inloop[u]) for (int v:nodes) if (!inloop[v]) {
            if (G[u][v] == 1 && belong[u] != belong[v]) return 0;
        }
    }
    build(ans);
    return 1;
}

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