Submission #303274

#	Time	Username	Problem	Language	Result	Execution time	Memory
303274		Kevin_Zhang_TW	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	270 ms	26200 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;
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();
    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;
}
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);
	}
    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:50:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   50 |     if (!build_ok(answer))
      |     ^~
supertrees.cpp:52:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   52 |  build(answer);
      |  ^~~~~

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