Submission #996401

#	Time	Username	Problem	Language	Result	Execution time	Memory
996401		phoenix	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	163 ms	30216 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"

using namespace std;

struct dsu {
    vector<int> p;
    vector<vector<int>> v;
    void init(int n) {
        p.resize(n);
        v.resize(n);
        for(int i = 0;i < n;i++) {
            p[ i ] = i;
            v[ i ].push_back({ i });
        }
    }
    int find(int x) {
        return p[ x ] = (p[ x ] == x ? p[ x ] : find(p[ x ]));
    }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(v[ a ].size() < v[ b ].size()) swap(a, b);
        for(int i = 0;i < v[ b ].size();i++) 
            v[ a ].push_back(v[ b ][ i ]);
        p[ b ] = a;
    }
};

const int N = 1000;
vector<vector<int>> rs;
vector<int> g[ N ];

int rt;
bool visited[ N ];
int dfs(int s, int rt) {
    visited[ s ] = 1;
    for(int c : g[ s ]) {
        if(visited[ c ])
            continue;
        rs[ s ][ c ] = 1;
        rs[ c ][ s ] = 1;
        return dfs(c, rt) + 1;
    }
    if(s != rt) {
        rs[ s ][ rt ] = 1;
        rs[ rt ][ s ] = 1;
    }
    return 1;
}

// void build(vector<vector<int>> p) {
//     for(auto c : p) {
//         for(int x : c) cout << x << ' ';
//         cout << '\n';
//     }
// }

int construct(vector<vector<int>> p) {
    int n = p.size();
    dsu ds;
    dsu ds0;
    ds.init(n);
    ds0.init(n);
    rs.resize(n, vector<int>(n));
    vector<pair<int, int>> e[3];
    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 ]) {
                ds0.unite(i, j);
                if(p[ i ][ j ] == 1)
                    ds.unite(i, j); 
            }         
            e[p[ i ][ j ]].push_back({i, j});
       }
    }
    for(pair<int, int> c : e[ 0 ]) 
        if(ds0.find(c.first) == ds0.find(c.second)) 
            return 0;
    for(pair<int, int> c : e[ 2 ]) 
        if(ds.find(c.first) == ds.find(c.second)) 
            return 0;
        else {
            g[ ds.find(c.first) ].push_back(ds.find(c.second));
            g[ ds.find(c.second) ].push_back(ds.find(c.first));
        }
    for(int i = 0;i < n;i++) {
        if(visited[ i ]) continue;
        if(dfs(i, i) == 2) return 0;
    }
    bool us[ n ] = {};
    for(int i = 0;i < n;i++) {
        if(us[ i ]) continue;
        int x = ds.find(i);
        for(int to : ds.v[ x ]) {
            if(to == x) continue;
            us[ to ] = 1;
            rs[ x ][ to ] = 1;
            rs[ to ][ x ] = 1;
        }
    }
    build(rs);
    return 1;
}

// int main() {
//     int n;
//     cin >> n;
//     vector<vector<int>> p(n, vector<int>(n));
//     for(int i = 0;i < n;i++) {
//         for(int j = 0;j < n;j++) {
//             cin >> p[i][j];
//         }
//     }
//     cout << construct(p);
// }

Compilation message (stderr)

supertrees.cpp: In member function 'void dsu::unite(int, int)':
supertrees.cpp:25:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = 0;i < v[ b ].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