Submission #303294

#	Time	Username	Problem	Language	Result	Execution time	Memory
303294		Kevin_Zhang_TW	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	263 ms	26260 KiB

supertrees

#include "supertrees.h"
#include <vector>

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 300010;
int g[maxn], sz[maxn], n, cnt[10];
int find(int i) { return g[i] == i ? g[i] : g[i] = find(g[i]); }
std::vector<std::vector<int>> p;
bool merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if ( sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    return g[b] = a, true;
}
void dsuinit() {
    for (int i = 0;i < n;++i)
        g[i] = i, sz[i] = 1;
}
bool build_ok(vector<vector<int>> &edge) {
    dsuinit();
    if (!cnt[2]) {
        for (int i = 0;i < n;++i)
            for (int j = i+1;j < n;++j)
                if (p[i][j] && merge(i, j))
                    edge[i][j] = edge[j][i] = true;
        for (int i = 0;i < n;++i)
            for (int j = i+1;j < n;++j)
                if (!p[i][j] && find(i) == find(j))
                    return false;
        return true;
    }
    if (!cnt[1] && !cnt[3]) {
        for (int i = 0;i < n;++i)
            for (int j = i+1;j < n;++j)
                if (p[i][j]) merge(i, j);
        for (int i = 0;i < n;++i)
            for (int j = i+1;j < n;++j)
                if (!p[i][j] && find(i) == find(j))
                    return false;
        vector<vector<int>> child(n);
        for (int i = 0;i < n;++i)
            child[ find(i) ].pb(i);
        for (int i = 0;i < n;++i) if (child[i].size() == 2)
            return false;
        for (int i = 0;i < n;++i) if (child[i].size() > 2) {
            int lst = child[i].back();
            for (int u : child[i]) {
                edge[lst][u] = edge[u][lst] = true;
                lst = u;
            }
        }
        return true;
    }
    assert(false);
}
int construct(std::vector<std::vector<int>> p) {
	n = p.size();
    ::p = p;
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(n);
		answer.push_back(row);
        for (int j = i+1;j < n;++j)
            ++cnt[ p[i][j] ];
	}

    if (!build_ok(answer))
        return 0;
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:78:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |     if (!build_ok(answer))
      |     ^~
supertrees.cpp:80:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   80 |  build(answer);
      |  ^~~~~

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