Submission #1315962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315962		rahidilbayramli	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	110 ms	26112 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define sz(v) (int)(v.size())
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int sz = 1e3+5;
int usize[sz], par[sz];
void makeset(int v)
{
    par[v] = v;
    usize[v] = 1;
}
int findpar(int v)
{
    if(par[v] == v)
        return v;
    return par[v] = findpar(par[v]);
}
void unionsets(int a, int b)
{
    a = findpar(a);
    b = findpar(b);
    if(a != b)
    {
        if(usize[a] > usize[b])
            swap(a, b);
        par[b] = a;
        usize[a] += usize[b];
    }
}
int construct(vector<vector<int>>p)
{
    int n = sz(p);
    int cnt = 0, cnt2 = 0, cnt3 = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cnt += p[i][j];
            cnt2 += (p[i][j] <= 1);
            cnt3 += ((p[i][j] % 2 == 0 && i != j) || (p[i][j] == 1 && i == j));
        }
    }
    if(cnt == n * n)
    {
        vector<vector<int>>answer;
        for(int i = 0; i < n; i++)
        {
            vector<int>row;
            for(int j = 0; j < n; j++)
            {
                if(j == i + 1 || j == i - 1)
                    row.pb(1);
                else
                    row.pb(0);
            }
            answer.pb(row);
        }
        build(answer);
        return 1;
    }
    if(cnt2 == n * n)
    {
        for(int i = 0; i < n; i++)
            makeset(i);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                    continue;
                if(p[i][j] == 1)
                    unionsets(i, j);
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int u = i, v = j;
                u = findpar(u);
                v = findpar(v);
                if(u == v && p[i][j] == 0)
                {
                    return 0;
                }
            }
        }
        vl v[n];
        int grid[n][n];
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                grid[i][j] = 0;
        }
        for(int i = 0; i < n; i++)
        {
            int u = i;
            u = findpar(u);
            if(i == u)
                continue;
            grid[u][i] = 1;
            grid[i][u] = 1;
        }
        vector<vector<int>>answer;
        for(int i = 0; i < n; i++)
        {
            vector<int>row;
            for(int j = 0; j < n; j++)
                row.pb(grid[i][j]);
            answer.pb(row);
        }
        build(answer);
        return 1;
    }
    if(cnt3 == n * n)
    {
        for(int i = 0; i < n; i++)
            makeset(i);
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i == j)
                    continue;
                if(p[i][j] == 2)
                    unionsets(i, j);
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int u = i, v = j;
                u = findpar(u);
                v = findpar(v);
                if(u == v && p[i][j] == 0)
                {
                    return 0;
                }
            }
        }
        int grid[n][n];
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                grid[i][j] = 0;
        }
        vi v[n];
        for(int i = 0; i < n; i++)
        {
            int u = i;
            u = findpar(u);
            v[u].pb(i);
        }
        for(int i = 0; i < n; i++)
        {
            if(sz(v[i]) > 1)
            {
                ll lst = v[i].back();
                for(auto u : v[i])
                {
                    grid[u][lst] = 1;
                    grid[lst][u] = 1;
                    lst = u;
                }
            }
        }
        vector<vector<int>>answer;
        for(int i = 0; i < n; i++)
        {
            vector<int>row;
            for(int j = 0; j < n; j++)
                row.pb(grid[i][j]);
            answer.pb(row);
        }
        build(answer);
        return 1;
    }
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:190:1: warning: control reaches end of non-void function [-Wreturn-type]
  190 | }
      | ^

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