Submission #683767

#	Time	Username	Problem	Language	Result	Execution time	Memory
683767		sharaelong	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	212 ms	24124 KiB

supertrees

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

struct DisjointSet {
    int n;
    vector<int> parent, rank;
    DisjointSet(int _n) : n(_n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
    }

    int find(int u) {
        return parent[u] = (u == parent[u] ? u : find(parent[u]));
    }

    void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) ++rank[v];
    }
};

int construct(vector<vector<int>> p) {
	int n = p.size();
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            if (p[i][j] == 3) {
                return 0;
            }
        }
    }

    DisjointSet dsu(n);
    DisjointSet dsu2(n);
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if (p[i][j] >= 1) {
                dsu.merge(i, j);
            }
            if (p[i][j] == 1) {
                dsu2.merge(i, j);
            }
        }
    }
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if (dsu.find(i) == dsu.find(j) && p[i][j] == 0) return 0;
            if (dsu2.find(i) == dsu2.find(j) && p[i][j] != 1) return 0;
            if (dsu.find(i) == dsu.find(j) && dsu2.find(i) != dsu2.find(j) && p[i][j] != 2) return 0;
        }
    }
    
    vector<vector<int>> ans(n, vector<int>(n, 0));
    vector<vector<int>> trees(n);
    for (int i=0; i<n; ++i) trees[dsu2.find(i)].push_back(i);
    for (int i=0; i<n; ++i) {
        // for (int x: trees[i]) cout << x << ' ';
        // cout << endl;
        for (int j=0; j+1<trees[i].size(); ++j) {
            int x = trees[i][j];
            int y = trees[i][j+1];
            ans[x][y] = ans[y][x] = 1;
        }
    }
    vector<vector<int>> comps(n);
    for (int i=0; i<n; ++i) {
        if (!trees[i].empty()) {
            comps[dsu.find(trees[i][0])].push_back(trees[i][0]);
        }
    }
    for (int i=0; i<n; ++i) {
        // for (int x: comps[i]) cout << x << ' ';
        // cout << endl;
        if (comps[i].size() == 2) return 0;
        for (int j=0; j+1<comps[i].size(); ++j) {
            int x = comps[i][j];
            int y = comps[i][j+1];
            ans[x][y] = ans[y][x] = 1;
        }
        if (comps[i].size() >= 3) ans[comps[i][0]][comps[i].back()] = ans[comps[i].back()][comps[i][0]] = 1;
    }
	build(ans);
	return 1;
}

Compilation message (stderr)

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

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