Submission #300284

#	Time	Username	Problem	Language	Result	Execution time	Memory
300284		couplefire	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	2 ms	672 KiB

supertrees

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

struct UnionFind{
    int parent[MAXN];
    int siz[MAXN];

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void make_set(int v) {
        parent[v] = v;
        siz[v] = 1;
    } 

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (siz[a] < siz[b])
                swap(a, b);
            parent[b] = a;
            siz[a] += siz[b];
        }
    }
};

int n;
int grid[MAXN][MAXN];
UnionFind u1;
bool ans1 = true;
vector<int> vv[MAXN];
bool b[MAXN][MAXN];

bool solve(vector<int> ps){
    if(ps.size() == 0) return true;
    int m = ps.size();
    UnionFind uone;
    for(auto i : ps) uone.make_set(i);
    for(int i = 0; i<m; i++){
        for(int j = 0; j<m; j++){
            if(grid[ps[i]][ps[j]] == 1) uone.union_sets(ps[i], ps[j]);
        }
    }
    for(int i = 0; i<m; i++){
        for(int j = 0; j<m; j++){
            if(grid[ps[i]][ps[j]] == 2 && uone.find_set(ps[i]) == uone.find_set(ps[j])){
                return false;
            }
        }
    }
    vector<int> comps[MAXN];
    for(int i = 0; i<m; i++) comps[uone.find_set(i)].push_back(i);
    int num = 0;
    vector<int> good;
    for(int i = 0; i<MAXN; i++) if(comps[i].size() > 0) num++, good.push_back(i);
    if(num == 2){
        return false;
    }
    for(int i = 0; i<good.size(); i++){
        for(int j = 0; j<comps[good[i]].size()-1; j++){
            b[comps[good[i]][j]][comps[good[i]][j+1]] = 1;
            b[comps[good[i]][j+1]][comps[good[i]][j]] = 1;
        }
        b[comps[good[i]][0]][comps[good[(i+1)%good.size()]][0]] = 1;
        b[comps[good[(i+1)%good.size()]][0]][comps[good[i]][0]] = 1;
    }
}

int calc(vector<vector<int>> p){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("a.in", "r", stdin);
    // cin >> n;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++) grid[i][j] = p[i][j];
    }
    for(int i = 0; i<n; i++) u1.make_set(i);
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++) if(grid[i][j] != 0) u1.union_sets(i, j);
    }
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(grid[i][j] == 0 && u1.find_set(i) == u1.find_set(j)){
                return 0;
            }
        }
    }
    // cout << "hi" << endl;
    for(int i = 0; i<n; i++){
        vv[u1.find_set(i)].push_back(i);
    }
    // for(int i = 0; i<n; i++) cout << u1.find_set(i) << endl;
    for(int i = 0; i<n; i++){
        if(!solve(vv[i])) return 0;
    }
    vector<vector<int>> bb(n, vector<int>(n));
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++) bb[i][j] = b[i][j];
    }
    build(bb);
    return 1;
}

int construct(vector<vector<int>> p){
    n = p.size();
    return calc(p);
}

Compilation message (stderr)

supertrees.cpp: In function 'bool solve(std::vector<int>)':
supertrees.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i<good.size(); i++){
      |                    ~^~~~~~~~~~~~
supertrees.cpp:66:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int j = 0; j<comps[good[i]].size()-1; j++){
      |                        ~^~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

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