Submission #414956

#	Time	Username	Problem	Language	Result	Execution time	Memory
414956		MKopchev	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	289 ms	24048 KiB

supertrees

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

//void build(std::vector<std::vector<int>> _b);

const int nmax=1e3+42;

int parent[nmax];
int root(int node)
{
    if(node==parent[node])return node;
    parent[node]=root(parent[node]);
    return parent[node];
}

vector< int > seen[nmax];

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

	for(int i=0;i<n;i++)parent[i]=i;

	for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(p[i][j])parent[root(i)]=root(j);

	for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(p[i][j]==0&&root(i)==root(j))return 0;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(p[i][j]==3)return 0;

    for(int i=0;i<n;i++)
        seen[root(i)].push_back(i);

	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	for(int i=0;i<n;i++)
        if(seen[i].size()>1)
        {
            vector<int> me=seen[i];

            for(auto w:me)parent[w]=w;

            for(auto u:me)
                for(auto v:me)
                    if(p[u][v]==1)parent[root(u)]=root(v);

            for(auto u:me)
                for(auto v:me)
                    if(p[u][v]==2&&root(u)==root(v))return 0;

            map<int, vector<int> > help={};

            for(auto u:me)
                help[root(u)].push_back(u);

            vector<int> starts={};

            for(auto w:help)
            {
                vector<int> path=w.second;

                starts.push_back(path[0]);

                for(int j=1;j<path.size();j++)
                {
                    int s=path[j-1];
                    int t=path[j];

                    answer[s][t]=1;
                    answer[t][s]=1;
                }
            }

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

            if(starts.size()>1)
            {
                for(int i=0;i<starts.size();i++)
                {
                    int u=starts[i];
                    int v=starts[(i+1)%starts.size()];

                    answer[u][v]=1;
                    answer[v][u]=1;
                }
            }
        }

	build(answer);
	return 1;
}
/*
static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}

void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}

int main() {
    assert(scanf("%d", &n) == 1);

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(p);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}
*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |     for(int i=0;i<n;i++)
      |     ^~~
supertrees.cpp:39:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  std::vector<std::vector<int>> answer;
      |  ^~~
supertrees.cpp:74:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 for(int j=1;j<path.size();j++)
      |                             ~^~~~~~~~~~~~
supertrees.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                 for(int i=0;i<starts.size();i++)
      |                             ~^~~~~~~~~~~~~~

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