Submission #560661

#	Time	Username	Problem	Language	Result	Execution time	Memory
560661		ahmet34	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	200 ms	24004 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int INF = 5e8, N = 1e5+10, M = 998244353, LOG = 16;
const ll LINF = 1e18;

struct DSU {
    vector<int> pr, sz;

    DSU (int n) : pr(n), sz(n, 1) {
        iota(all(pr), 0);
    }
    int find_par(int x) {
        return pr[x] = (pr[x] == x ? x : find_par(pr[x]));
    }
    bool unite(int a, int b) {
        a = find_par(a), b = find_par(b);
        if(a == b) return false;

        if(sz[a] < sz[b]) swap(a, b);
        pr[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int construct(vector<vector<int>> p) {
    for(const auto& vi : p) if(count(all(vi), 3)) return 0;
    
    int n = p.size();
    vector<vector<int>> ans(n, vector<int>(n));

    DSU sets(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(i != j and p[i][j] == 1 and sets.unite(i, j)) 
                ans[i][j] = ans[j][i] = 1;
        }
    }

    set<int> parents;
    DSU cmp(n);

    for(int i = 0; i < n; ++i)
        parents.insert(sets.find_par(i));
    
    while(!parents.empty()) {
        vector<int> cur {*parents.begin()};

        for(int x : parents) 
            if(p[cur[0]][x] == 2) {
                cmp.unite(x, cur[0]);
                cur.push_back(x);
            }

        if(cur.size() == 2) return 0;
        for(int x : cur) parents.erase(x);
        
        for(int i = 0; i < cur.size(); i++) {
            int a = cur[i], b = cur[(i+1)%cur.size()];
            if(a != b)
                ans[a][b] = ans[b][a] = 1;
        }
    }
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            int x = sets.find_par(i), y = sets.find_par(j);
            
            if(p[i][j] == 2) 
                if(x == y or cmp.find_par(x) != cmp.find_par(y))
                    return 0;
            
            if(p[i][j] == 1 and x != y) return 0;

            if(p[i][j] == 0 and cmp.find_par(x) == cmp.find_par(y)) 
                return 0;
        }
    build(ans);
    return 1;
}

Compilation message (stderr)

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

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