Submission #591182

#	Time	Username	Problem	Language	Result	Execution time	Memory
591182		SirCovidThe19th	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	205 ms	22036 KiB

supertrees

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

#define FOR(i, x, y) for (int i = x; i < y; i++)

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

    vector<vector<int>> ans(n, vector<int>(n, 0));
    bool vis[n] = {}; 
    int par[n]; iota(par, par + n, 0);

    function<int(int)> get = [&](int i){
        return i == par[i] ? i : par[i] = get(par[i]);
    };
    auto merge = [&](int a, int b){
        par[get(a)] = get(b);
    };
    FOR(src, 0, n) if (!vis[src]){
        bool incmp[n] = {}; vector<int> cmp; 
        FOR(i, 0, n) if (p[src][i])
            cmp.push_back(i), incmp[i] = 1;
    
        for (int i : cmp) for (int j : cmp) 
            if (p[i][j] == 1) merge(i, j);
            
        for (int i : cmp){ //check here
            if (vis[i]) return 0;
            FOR(j, 0, n)
                if (p[i][j] and !incmp[j]) return 0;
            for (int j : cmp)
                if (!((get(i) == get(j) and p[i][j] == 1) or (get(i) != get(j) and p[i][j] == 2)))
                    return 0;
        }
        for (int i : cmp) vis[i] = 1;

        bool use[n] = {}; vector<int> head;
        for (int i : cmp){
            int c = get(i);
            if (!use[c]) head.push_back(c), use[c] = 1;
            if (i != c) ans[i][c] = ans[c][i] = 1;
        }
        FOR(i, 0, head.size()){
            int a = head[i];
            int b = head[(i + 1) % head.size()];
            if (a != b) ans[a][b] = ans[b][a] = 1;
        }
    }
    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, x, y) for (int i = x; i < y; i++)
......
   45 |         FOR(i, 0, head.size()){
      |             ~~~~~~~~~~~~~~~~~           
supertrees.cpp:45:9: note: in expansion of macro 'FOR'
   45 |         FOR(i, 0, head.size()){
      |         ^~~

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