Submission #1077890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077890		anango	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	173 ms	24400 KiB

supertrees

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

class DSU {
private: int n; vector<int> parent,rank;
public:
    DSU(int sz) {
        n=sz; parent=vector<int>(n); iota(parent.begin(), parent.end(), (int)0); rank=vector<int>(n,0);
    }
    int find(int node) {
        return (node==parent[node])?(node):(parent[node] = find(parent[node]));
    }
    void link(int u, int v){ 
        u=find(u); v=find(v); if (rank[u]<rank[v]) swap(u,v);
        rank[u]+=rank[u]==rank[v]; parent[v] = u;
    }
    vector<int> getpars() {
        for (int i=0; i<n; i++) find(i);
        return parent;
    }
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	DSU dsu(n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (p[i][j]!=0) {
                dsu.link(i,j);
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (p[i][j]==3) {
                return 0;
            }
            if (dsu.find(i)==dsu.find(j) && p[i][j]==0) {
                return 0;
            } 
        }
    }
    vector<int> par = dsu.getpars();
    map<int,vector<int>> compar;
    for (int i=0; i<n; i++) {
        compar[par[i]].push_back(i);
    }
    vector<vector<int>> components;
    for (auto i:compar) {
        components.push_back(i.second);
    }
    vector<vector<int>> ans(n,vector<int>(n,0));
    for (auto component:components) {
        sort(component.begin(), component.end());
        int k = component.size();
        //if p[i][j] = 1, they are on the same vertex of the cycle
        //otherwise we have no additional info of which vertices are on the cycle, just choose it arbitrarily
        DSU dsu2(k);
        map<int,int> rev; for (int i=0; i<k; i++) rev[component[i]] = i;
        for (int i:component) {
            for (int j:component) {
                if (p[i][j]==1) {
                    dsu2.link(rev[i],rev[j]);
                }
            }
        }
        map<int,vector<int>> cycloc;
        vector<int> par2 = dsu2.getpars();
        for (int i=0; i<k; i++) {
            cycloc[par2[i]].push_back(i);
        }
        vector<vector<int>> cyclecom;
        for (auto i:cycloc) {
            cyclecom.push_back(i.second);
        }
        if (cyclecom.size()>1) {
            for (int i=0; i<cyclecom.size(); i++) {
                int rep = cyclecom[i][0];
                int rep1 = cyclecom[(i+1)%cyclecom.size()][0];
                ans[component[rep]][component[rep1]] = ans[component[rep1]][component[rep]] = 1;
            }
        }
        for (auto i:cyclecom) {
            for (int j=1; j<i.size(); j++) {
                int i1 = i[j-1];
                int i2 = i[j];
                ans[component[i1]][component[i2]] = ans[component[i2]][component[i1]] = 1;
            }
        }
        for (int i=0; i<k; i++) {
            for (int j=0; j<k; j++) {
                if (par2[i]==par2[j]) {
                    if (p[component[i]][component[j]]==2) {
                        return 0;
                    }
                }
                else {
                    if (p[component[i]][component[j]]==1) {
                        return 0;
                    }
                }
            }
        }
        if (cyclecom.size()==2) {
            return 0;
        }
    }
    build(ans);
	return 1;
}

Compilation message (stderr)

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