Submission #1007444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007444		u_suck_o	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	126 ms	22208 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
#define MAXN 1005

using namespace std;

int N;
int sizes[MAXN], par[MAXN];
vector<int> comps[MAXN], comps1[MAXN];
vector<vector<int>> answer;

int find(int u) {
    if (u != par[u])
        par[u] = find(par[u]);
    return par[u];
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    //answer[u][v] = 1;
    //answer[v][u] = 1;
    if (sizes[u] > sizes[v]) {
        par[v] = u;
        sizes[u] += sizes[v];
    } else {
        par[u] = v;
        sizes[v] += sizes[u];
    }
}

void reset_dsu() {
    for (int i = 0; i < N; i++) {
        par[i] = i;
        sizes[i] = 1;
    }
}
int construct(vector<vector<int>> p) {
    N = p.size();
    answer = vector<vector<int>>(N, vector<int>(N, 0));
    
    //run dsu
    reset_dsu();
    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])
                join(i, j);
        }
    }
    //build components
    for (int i = 0; i < N; i++)
        comps[find(i)].push_back(i);
    
    //run dsu again to find comps of 1
    reset_dsu();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < comps[i].size(); j++) {
            for (int k = j+1; k < comps[i].size(); k++) {
                int x = comps[i][j], y = comps[i][k];
                if (p[x][y] == 0) return 0;
                if (p[x][y] == 1) join(x, y);
            }
        }
    }
    vector<int> reps;
    for (int i = 0; i < N; i++)
        comps1[find(i)].push_back(i);
    
    //check validity
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (find(i) == find(j) && p[i][j] != 1)
                return 0;
        }
    }
    
    //build paths
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < ((int) comps1[i].size())-1; j++) {
            answer[comps1[i][j]][comps1[i][j+1]] = 1;
            answer[comps1[i][j+1]][comps1[i][j]] = 1;
        }
    }
    
    //build rings
    for (int i = 0; i < N; i++) {
        vector<int> reps;
        for (int j : comps[i]) {
            if (j == find(j))
                reps.push_back(j);
        }
        int rsize = reps.size();
        if (rsize <= 1) continue;
        if (rsize == 2)
            return 0;
        for (int j = 0; j < rsize - 1; j++) {
            answer[reps[j]][reps[j+1]] = 1;
            answer[reps[j+1]][reps[j]] = 1;
        }
        answer[reps[0]][reps[rsize-1]] = 1;
        answer[reps[rsize-1]][reps[0]] = 1;
    }
    build(answer);
    return 1;
}

Compilation message (stderr)

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

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