Submission #428866

#	Time	Username	Problem	Language	Result	Execution time	Memory
428866		ACmachine	Connecting Supertrees (IOI20_supertrees)	C++17	65 / 100	392 ms	193732 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j);i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
using namespace std;

struct dsu{
    vector<int> p;
    int n;
    dsu(int _n){
        p.resize(n, -1);
    }
    int find(int x){
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool sameSet(int u, int v){
        return (find(u) == find(v));
    }
    bool join(int a, int b){
        a = find(a); b = find(b);
        if(a == b) 
            return false;
        if(p[a] > p[b])
            swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};
int construct(vector<vector<int>> p) {
	int n = p.size();
    REP(i, n){
        REP(j, n){
            if(p[i][j] == 3)
                return 0;
        }
    }
	vector<vector<int>> answer(n, vector<int>(n, 0));
	dsu d(n);
    REP(i, n){
        REP(j, i){
            if(p[i][j] == 1)
                d.join(i, j);
        }
    }
    REP(i, n){
        if(d.find(i) != i){
            int rp = d.find(i);
            answer[rp][i] = answer[i][rp] = 1;
        }
    }
    dsu d2(n); // with 2s. if multiple 1 repres are in same comp, then create cycle from them;
    REP(i, n){
        REP(j, i){
            if(p[i][j] == 2)
                d2.join(i, j);
        }
    }
    vector<vector<int>> buckets(n);
    REP(i, n){
        if(d.find(i) == i){
            buckets[d2.find(i)].pb(i);
        }
    }
    // can't be 2 in p[i][j] = 2;
    REP(i, n){
        if(buckets[i].size() == 2)
            return 0;
        if(buckets[i].size() > 2){
            REP(j, buckets[i].size()){
                int u = buckets[i][j];
                int v = buckets[i][(j + 1) % buckets[i].size()];
                answer[u][v] = answer[v][u] = 1;
            }
        }
    }
    // now some connectivity checks;
    // d2 is final connectivity; d are 1 components
    // if p[i][j] == 0; they cant be connected in any way
    // if p[i][j] == 2, they can't be connected in d;
    REP(i, n){
        REP(j, i){
            if(p[i][j] == 0 && d2.sameSet(i, j))
                return 0;
            if(p[i][j] == 2 && d.sameSet(i, j))
                return 0;
        }
    }
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
supertrees.cpp:5:19: note: in expansion of macro 'FOR'
    5 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
supertrees.cpp:74:13: note: in expansion of macro 'REP'
   74 |             REP(j, buckets[i].size()){
      |             ^~~
supertrees.cpp:15:18: warning: 'd.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |         p.resize(n, -1);
      |                  ^
supertrees.cpp:15:18: warning: 'd2.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |         p.resize(n, -1);
      |                  ^
supertrees.cpp:15:18: warning: 'd2.dsu::n' may be used uninitialized in this function [-Wmaybe-uninitialized]

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