Submission #300525

#	Time	Username	Problem	Language	Result	Execution time	Memory
300525		davitmarg	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	273 ms	26360 KiB

supertrees

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 1005;

#ifndef death
#include "supertrees.h"
#endif

#ifdef death

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

#endif

int parent[N];

void init(int n)
{
    for (int i = 0; i < n; i++)
        parent[i] = i;
}

int par(int v)
{
    if (v == parent[v])
        return v;
    return parent[v] = par(parent[v]);
}

void dsu(int a, int b)
{
    a = par(a);
    b = par(b);
    if (a == b)
        return;
    parent[b] = a;
}

int n,z;
vector<vector<int>> ans,p;

void add(int a, int b)
{
    ans[a][b] = ans[b][a] = 1;
}

void solve(vector<int> v)
{
    init(v.size());
    for (int i = 0; i < v.size(); i++)
        for (int j = i + 1; j < v.size(); j++)
            if (p[v[i]][v[j]] == 1)
                dsu(i, j);

    for (int i = 0; i < v.size(); i++)
        for (int j = i + 1; j < v.size(); j++)
            if (p[v[i]][v[j]] == 2 && par(i) == par(j))
            {
                z = 1;
                return;
            }
    map<int, vector<int>> VS;
    vector<int> V;
    for (int i = 0; i < v.size(); i++)
        VS[v[par(i)]].PB(v[i]);

    for (auto it = VS.begin(); it != VS.end(); ++it)
    {
        for (int i = 0; i < it->second.size() - 1; i++)
            add(it->second[i], it->second[i + 1]);
        V.push_back(it->first);
    }

    if(V.size()>1)
        for (int i = 0; i < V.size(); i++)
            add(V[i], V[(i + 1) % V.size()]);
}

int construct(vector<vector<int>> P)
{
    p = P;
    n = p.size();
    ans.resize(n, vector<int>(n,0));
    init(n);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (p[i][j])
            {
                dsu(i, j);
                if (p[i][j] == 3)
                    return 0;
            }

    map<int, vector<int>> vs;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
            if (p[i][j] == 0 && par(i) == par(j))
                return 0;
        vs[par(i)].push_back(i);
    }

    for (auto it = vs.begin(); it != vs.end(); ++it)
        solve(it->second);
    if (z)
        return 0;
    build(ans);
    return 1;
}

#ifdef death
int main()
{
    fastIO;
    vector<vector<int>> P;

    int nn;
    cin >> nn;
    for (int i = 0; i < nn; i++)
    {
        P.push_back(vector<int>());
        for (int j = 0; j < nn; j++)
        {
            int x;
            cin >> x;
            P[i].push_back(x);
        }
    }

    cout << construct(P) << endl;
    return 0;
}
#endif
/*

4
1 1 0 0 
1 1 0 0 
0 0 1 1 
0 0 1 1 

*/

Compilation message (stderr)

supertrees.cpp: In function 'void solve(std::vector<int>)':
supertrees.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:87:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int j = i + 1; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
supertrees.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:92:31: 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 = i + 1; j < v.size(); j++)
      |                             ~~^~~~~~~~~~
supertrees.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
supertrees.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int i = 0; i < it->second.size() - 1; i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int i = 0; i < V.size(); i++)
      |                         ~~^~~~~~~~~~

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