Submission #303614

#	Time	Username	Problem	Language	Result	Execution time	Memory
303614		nicolaalexandra	Connecting Supertrees (IOI20_supertrees)	C++14	Compilation error	0 ms	0 KiB

supertrees

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

int t[DIM],t2[DIM],a[DIM][DIM],f[DIM],last[DIM];
vector <int> v[DIM],w;

/*void build (vector <vector <int> > a){
    int n = a.size();
    for (int i=0;i<n;i++,cout<<"\n")
        for (int j=0;j<n;j++)
            cout<<a[i][j]<<" ";
}
*/
int get_rad (int t[], int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void uneste (int t[], int x, int y){
    int radx = get_rad (t,x), rady = get_rad (t,y);
    if (radx == rady)
        return;
    if (t[radx] > t[rady])
        swap (radx,rady);

    t[radx] += t[rady];
    t[rady] = radx;
}

int construct (vector <vector<int> > p){
    int n = p.size();

    memset (t,-1,sizeof t);
    memset (f,0,sizeof f);
    for (int i=1;i<=n;i++)
        v[i].clear();

    int ok = 0;
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
            if (p[i][j]){
                uneste (t,i+1,j+1);
                if (p[i][j] == 3)
                    ok = 1;
            }

    if (ok)
        return 0;

    int nr_comp = 0;
    for (int i=1;i<=n;i++){
        int rad = get_rad (t,i);
        if (!f[rad])
            f[rad] = ++nr_comp;

        v[nr_comp].push_back(i);
    }

    for (int i=1;i<=nr_comp;i++){

        /// fac iar paduri cu nodurile din multimea asta
        memset (t2,-1,sizeof t2);
        memset (last,0,sizeof last);

        for (auto it : v[i]){
            for (auto it2 : v[i]){
                if (it != it2 && p[it-1][it2-1] == 1)
                    uneste (t2,it,it2);
            }}

        w.clear();
        for (auto it : v[i]){

            int rad = get_rad (t2,it);
            if (t2[rad] == -1){
                w.push_back(it);
                continue;
            }

            if (!last[rad]){
                last[rad] = it;
                w.push_back(it);
            } else {
                a[last[rad]][it] = a[it][last[rad]] = 1;
                last[rad] = it;
            }
        }

        for (int j=0;j<w.size()-1;j++)
            a[w[j]][w[j+1]] = a[w[j+1]][w[j]] = 1;

        if (w.size() > 1)
            a[w[0]][ w[w.size()-1] ] = a[ w[w.size()-1] ][w[0]] = 1;
    }

    vector <vector<int> > ans;
    for (int i=1;i<=n;i++){
        vector <int> lin;
        for (int j=1;j<=n;j++)
            lin.push_back(a[i][j]);

        ans.push_back (lin);
    }

    build (ans);

    return 1;

}


int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    int n,i,j,x;
    vector <vector<int> > a;

    cin>>n;
    for (i=1;i<=n;i++){
        vector <int> lin;
        for (j=1;j<=n;j++){
            cin>>x;
            lin.push_back(x);
        }
        a.push_back(lin);
    }

    construct(a);


    return 0;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j=0;j<w.size()-1;j++)
      |                      ~^~~~~~~~~~~
/tmp/ccI8ekfT.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccOS7MN1.o:supertrees.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status