Submission #1016000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016000		deera	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	157 ms	27476 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<int> dist = {0, 0, 0, 0};

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dist[p[i][j]]++;

    // subtask 1
    // p[i][j] ==0
    // just a line
    if (dist[1] == n*n) {
        vector<vector<int>> r(n, vector<int>(n));
        for(int i=0;i<n-1;i++) {
            r[i][(i+1)%n] = 1;
            r[(i+1)%n][i] = 1;
        }

        build(r);
        return 1;
    }

    // substask 2
    // p[i][j] == 0 or 1
    // set of disconnected lines
    if(dist[2] == 0 && dist[3] == 0) {
        set<vector<int>> lines;

        for(int i=0;i<n;i++) {
            lines.insert(p[i]);
        }



        vector<vector<int>> r(n, vector<int>(n));
        vector<int> dupes(n);

        for (auto line: lines) {
            vector<int> points;
            for(int i=0;i<n;i++)
                if (line[i] == 1) 
                    points.push_back(i), dupes[i]++;

            for(int i=1;i<points.size();i++) {
                int a = points[i-1], b=points[i];

                r[a][b] = 1;
                r[b][a] = 1;
            }
        }

        for(auto i: dupes) 
            if (i > 1) return 0;

        build(r);
        return 1;
    }

    // substask 3
    // p[i][j] == 0 or 2 (except for i==j)
    // set of disconnected rings
    if(dist[1] == n && dist[3] == 0) {
        set<vector<int>> lines;

        for(int i=0;i<n;i++) {
            vector<int> line(n);
            for(int j=0;j<n;j++) {
                if (i == j && p[i][j] != 1) {
                    return 0;
                }
                line[j] = (int)(p[i][j] > 0);
            }
            lines.insert(line);
        }



        vector<vector<int>> r(n, vector<int>(n));
        vector<int> dupes(n);

        for (auto line: lines) {
            vector<int> points;
            for(int i=0;i<n;i++)
                if (line[i] == 1) 
                    points.push_back(i), dupes[i]++;

            // single point not connected to anything
            // (except itself)
            if (points.size() == 1) {
                continue;
            }
            
            // you need atleast 3 nodes to make a ring
            // without having multiple edges between 
            // two nodes
            if (points.size() < 3) {
                return 0;
            }

            for(int i=1;i<points.size();i++) {
                int a = points[i-1], b=points[i];

                r[a][b] = 1;
                r[b][a] = 1;
            }

            int a = points[0], b=points.back();
            r[a][b] = 1;
            r[b][a] = 1;
        }

        for(auto i: dupes) 
            if (i > 1) return 0;

        build(r);
        return 1;

    }

    return 0;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int i=1;i<points.size();i++) {
      |                         ~^~~~~~~~~~~~~~
supertrees.cpp:105:26: 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=1;i<points.size();i++) {
      |                         ~^~~~~~~~~~~~~~

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