Submission #310570

#	Time	Username	Problem	Language	Result	Execution time	Memory
310570		DS007	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	329 ms	22392 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1005;
 
class DSU {
    int par[N], n;
    
public:
    DSU(int n) {
        this->n = n;
        iota(par, par + n, 0);
    }
    
    int find(int x) {
        if (x == par[x])
            return x;
        return par[x] = find(par[x]);
    }
    
    void merge(int u, int v) {
        u = find(u), v = find(v);
        par[u] = v;
    }
};
 
int construct(vector<vector<int>> p) {
    int n = p.size();
    DSU dsu(n);
  
  	if (n == 1) {
      build({{0}});
      return 1;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3)
                return 0;
          else if (p[i][j] != 0)
            dsu.merge(i, j);
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
                return 0;
        }
    }
    
    vector<vector<int>> comp(n);
    vector<vector<int>> b(n);
    for (int i = 0; i < n; i++) b[i].resize(n, 0);
    vector<bool> done(n, false);
    
    for (int i = 0, k = 0; i < n; i++) {
        if (done[i])
            continue;
            
        comp[k].push_back(i);
        for (int j = i + 1; j < n; j++) {
            if (dsu.find(i) == dsu.find(j))
                comp[k].push_back(j), done[j] = true;
        }
        k++;
    }
    
    for (int i = 0; i < comp.size() && !comp[i].empty(); i++) {
        //cout << "Done" << endl;
      if (comp[i].size() == 1) continue;
      
        set<int> s;
        for (int j = 0; j < comp[i].size(); j++) {
            for (int k = 0; k < comp[i].size(); k++) {
                if (k != j && p[comp[i][j]][comp[i][k]] == 1)
                    s.insert(comp[i][j]), s.insert(comp[i][k]);
            }
        }
        
        for (int j : s) {
            for (int k : s) {
                if (k != j && p[j][k] != 1)
                    return 0;
            }
        }
        
        if (s.size() == comp[i].size() - 1)
            return 0;
            
        if (s.empty()) {
            if (comp[i].size() <= 2)
                return 0;
                
            int last = -1;
            for (int j : comp[i]) {
                if (last != -1)
                    b[j][last] = b[last][j] = 1;
                last = j;
            }
            b[*comp[i].begin()][*comp[i].rbegin()] = b[*comp[i].rbegin()][*comp[i].begin()] = 1;
        }
        
        int last = -1;
        for (int j : s) {
            if (last != -1)
                b[j][last] = b[last][j] = 1;
            last = j;
        }
        
        int last1 = -1, first1 = -1;
        for (int j : comp[i]) {
            if (s.count(j))
                continue;
            if (last1 != -1)
                b[last1][j] = b[j][last1] = 1;
            else
                first1 = j;
            last1 = j;
        }
        
      	if (s.size() != comp[i].size()) {
            if (last != -1 && first1 != -1)
        	b[last][first1] = b[first1][last] = 1;
            if (last != -1 && last1 != -1)
        	b[last][last1] = b[last1][last] = 1;
        }
    }
    
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < comp.size() && !comp[i].empty(); i++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:74:27: 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 = 0; j < comp[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
supertrees.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (int k = 0; k < comp[i].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~

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