Submission #456130

#	Time	Username	Problem	Language	Result	Execution time	Memory
456130		fuad27	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1174 ms	2097156 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>

using namespace std;
void dfs(int u, vector < int > & cc, vector < bool > & vis, vector < vector < int >> adj) {
    vis[u] = true;
    cc.push_back(u);
    for (int to: adj[u])
        if (!vis[to]) {
            dfs(to, cc, vis, adj);
        }
}
int construct(std::vector < std::vector < int >> p) {
    int n = p.size();
    vector < vector < int >> adj(n);
    bool two = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (p[i][j]) {
                two |= p[i][j] == 2;
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
    }
    vector < int > cc;
    vector < bool > vis(n);
    vector < vector < int >> answer(n, vector < int > (n, 0));
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(i, cc, vis, adj);
            int m = cc.size();
            int edges = 0;
            for (int p: cc)
                edges += adj[p].size();
            edges /= 2;
            if (m == 2 && two)
                return 0;
            for (int j = 0; j < m - 1; j++)
                answer[cc[j]][cc[j + 1]] = answer[cc[j + 1]][cc[j]] = 1;
            if (m > 2 && two)
                answer[cc[0]][cc[m - 1]] = answer[cc[m - 1]][cc[0]] = 1;
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < m; k++) {
                    if (p[cc[j]][cc[k]] == 0)
                        return 0;
                }
            }
            cc.clear();
        }
    }
    build(answer);
    return 1;
}

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