Submission #303630

#	Time	Username	Problem	Language	Result	Execution time	Memory
303630		nicolaalexandra	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	262 ms	26236 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;

        /// mai verific daca e conectat cu toate nodurile din componenta
        for (auto it : v[f[rad]]){
            if (p[it-1][i-1] == 0)
                return 0;
        }

        v[f[rad]].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;
            }
        }

        if (w.size() == 2)
            return 0;

        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;

}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int j=0;j<w.size()-1;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