Submission #542136

#	Time	Username	Problem	Language	Result	Execution time	Memory
542136		Lobo	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	248 ms	24260 KiB

supertrees

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e3 + 10;

int n, ds[maxn], ds1[maxn];
vector<int> vec[maxn], vec1[maxn];

int find(int v) {
    if(v == ds[v]) return v;
    return ds[v] = find(ds[v]);
}

void join(int u, int v) {
    ds[v] = u;

    for(auto x : vec[v]) vec[u].pb(x);
}


int find1(int v) {
    if(v == ds1[v]) return v;
    return ds1[v] = find1(ds1[v]);
}

void join1(int u, int v) {
    ds1[v] = u;

    for(auto x : vec1[v]) vec1[u].pb(x);
}


int construct(vector<vector<int>> p) {
    n = p.size();
    int ans = 1;
    for(int i = 0; i < n; i++) {
        ds[i] = i;
        vec[i].pb(i);
    }
    
    //juntar os 1s
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(p[i][j] == 1 && find(i) != find(j)) join(find(i),find(j));
        }
    }

    for(int i = 0; i < n; i++) {
        // cout << i << " " << find(i) << endl;
        if(find(i) != i) continue;
        //compara i com todos no vec dele

        for(auto x : vec[i]) {
            if(i == x) continue;
            if(p[x][i] == 0) ans = 0;

            for(int j = 0; j < n; j++) {
                if(p[x][j] != p[i][j] && x != j && x != i) ans = 0;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        ds1[i] = i;
        vec1[i].pb(i);
    }

    //junta os caras que sao pais e tem p[i][j] = 2

    for(int i = 0; i < n; i++) {

        for(int j = i+1; j < n; j++) {
            if(p[i][j] != 2) continue;

            int i1 = find1(find(i));
            int j1 = find1(find(j));
            
            if(i1 != j1) join1(i1,j1);
        }
    }

    //testar se deu bom
    for(int i = 0; i < n; i++) {
        if(vec1[find1(find(i))].size() == 2) ans = 0;

        for(int j = i+1; j < n; j++) {
            if(find(i) == find(j)) {
                if(p[i][j] != 1) ans = 0;
            }

            if(find1(find(i)) != find1(find(j))) {
                if(p[i][j] != 0) ans = 0;
            }

            if(find1(find(i)) == find1(find(j)) && find(i) != find(j)) {
                if(p[i][j] != 2) ans = 0;
            }
        }
    }

    if(ans == 0) return 0;

    vector<vector<int>> b(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) b[i].pb(0);
    }

    //ligo com as arestas dos 1s
    for(int i = 0; i < n; i++) {
        if(find(i) != i) continue;

        for(int j = 1; j < vec[i].size(); j++) {
            b[vec[i][j-1]][vec[i][j]] = 1;
            b[vec[i][j]][vec[i][j-1]] = 1;
        }
    }

    //ligo as arestas dos 2s
    for(int i = 0; i < n; i++) {
        if(i != find1(find(i)) || vec1[i].size() == 1) continue;

        for(int j = 0; j < vec1[i].size(); j++) {
            b[vec1[i][j]][vec1[i][(j+1)%((int) vec1[i].size())]] = 1;
            b[vec1[i][(j+1)%((int) vec1[i].size())]][vec1[i][j]] = 1;
        }
    }

    build(b);

    // for(int i = 0; i < n; i++) {
    //     for(int j = 0; j < n; j++) {
    //         cout << i << " " << j << "  " << b[i][j] << endl;
    //     }
    // }
    return 1;
}


// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     // freopen("out.out", "w", stdout);

//     int N;
//     vector<vector<int>> p;
//     cin >> N;
//     p.resize(N);
//     for(int i = 0; i < N; i++) {
//         for(int j = 0; j < N; j++) {
//             int x; cin >> x;
//             p[i].pb(x);
//         }
//     }

//     construct(p);

// }

Compilation message (stderr)

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

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