Submission #768773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768773	2023-06-28T15:04:36 Z	AlesL0	Connecting Supertrees (IOI20_supertrees)	C++17	Compilation error	0 ms	0 KB

supertrees

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <ll> P, H;
vector <vector <int>> sol;

ll dsu_find(ll x){
    if (P[x] == x)return x;
    return (P[x] = dsu_find(P[x]));
}

void dsu_union(ll x, ll y){
    x = dsu_find(x), y = dsu_find(y);
    if (x == y)return;
    if (H[x] > H[y])P[y] = x;
    if (H[x] < H[y])P[x] = y;
    if (H[x] == H[y]){
        P[y] = x;
        H[x]++;
    }
}

bool cmp(ll a, ll b){
    return (P[a] < P[b]);
}

bool solve(vector <ll> &v, vector <vector <int>> &p){
    ll n = v.size();
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++)if (p[v[i]][v[j]] == 1)dsu_union(v[i], v[j]);
    }
    for (int i = 0; i < n; i++)P[v[i]] = dsu_find(v[i]);
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)if (p[v[i]][v[j]] == 2 && P[v[i]] == P[v[j]])return 0;
    }
    sort(v.begin(), v.end(), cmp);
    ll current = 0;
    for (int i = 1; i < n; i++){
        if (P[v[i]] == P[v[i-1]]){
            sol[v[i]][v[i-1]] = 1;
            sol[v[i-1]][v[i]] = 1;
        }
        else {
            sol[v[i]][v[current]] = 1;
            sol[v[current]][v[i]] = 1;
            current = i;
        }
    }
    sol[v[current]][v[0]] = 1;
    sol[v[0]][v[current]] = 1;
    return 1;
}

void build(vector <vector <int>> b){
    /*for (int i = 0; i < b.size(); i++){
        cerr << endl;
        for (int j = 0; j < b.size(); j++){
            cerr << b[i][j] << " ";
        }
    }*/
    return;
}

int construct(vector <vector <int>> p){
    ll n = p.size();
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++)if (p[i][j] == 3)return 0;
    }
    P.resize(n);
    H.resize(n, 0);
    for (int i = 0; i < n; i++)P[i] = i;
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++)if (p[i][j] > 0)dsu_union(i, j);
    }
    for (int i = 0; i < n; i++)P[i] = dsu_find(i);
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++)if (p[i][j] == 0 && P[i] == P[j])return 0;
    }
    vector <pair<ll, ll>> t(n);
    for (int i = 0; i < n; i++)t[i] = {P[i], i};
    sort(t.begin(), t.end());
    sol.resize(n, vector <int> (n, 0));
    for (int i = 0; i < n; i++){
        P[i] = i;
        H[i] = 0;
    }
    vector <ll> v;
    for (int i = 0; i < n; i++){
        if (i > 0 && t[i].first != t[i-1].first){
            if (!solve(v, p))return 0;
            v.clear();
        }
        v.push_back(t[i].second);
    }
    if (!solve(v, p))return 0;
    for (int i = 0; i < n; i++)sol[i][i] = 0;
    build(sol);
    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);
}*/

/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
*/

Compilation message

/usr/bin/ld: /tmp/cctvr2Pz.o: in function `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)':
grader.cpp:(.text+0x260): multiple definition of `build(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'; /tmp/ccrtajoy.o:supertrees.cpp:(.text+0x770): first defined here
collect2: error: ld returned 1 exit status