Submission #303320

#	Time	Username	Problem	Language	Result	Execution time	Memory
303320		Kevin_Zhang_TW	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	268 ms	26360 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 n, cnt[10];
std::vector<std::vector<int>> p;
struct dsu {
    int g[maxn], sz[maxn];
    int find(int i) { return g[i] == i ? g[i] : g[i] = find(g[i]); }
    void init() {
        for (int i = 0;i < n;++i)
            g[i] = i, sz[i] = 1;
    }
    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;
    }
    int operator()(int i) { return find(i); }
}d1, d2;
bool C1() {
    d1.init();
    for (int i = 0;i < n;++i)
        for (int j = i+1;j < n;++j)
            if (p[i][j])
                d1.merge(i, j);
    for (int i = 0;i < n;++i)
        for (int j = i+1;j < n;++j)
            if (!p[i][j] && d1(i) == d1(j))
                return false;
    return true;
}
void M1() {
    d1.init();
    for (int i = 0;i < n;++i)
        for (int j = i+1;j < n;++j)
            if (p[i][j] == 1)
                d1.merge(i, j);
}
void M2() {
    d2.init();
    for (int i = 0;i < n;++i)
        for (int j = i+1;j < n;++j)
            if (p[i][j] == 2) 
                d2.merge(i, j);
}
bool build_ok(vector<vector<int>> &edge) {
    if (!C1()) return false;
    M1(), M2();
    vector<vector<int>> c1(n), c2(n);
    for (int i = 0;i < n;++i) 
        c1[d1(i)].pb(i), c2[d2(i)].pb(i);
    // connect same chain
    for (int i = 0;i < n;++i) {
        if (c1[i].size() > 1) {
            int lst = -1;
            for (int u : c1[i]) {
                if (lst != -1) 
                    edge[lst][u] = edge[u][lst] = true;
                lst = u;
            }
        }
    }
    // check valid
    for (int i = 0;i < n;++i)
        for (int j = i+1;j < n;++j) {
            if (p[i][j] != 1 && d1(i) == d1(j))
                return false;
            if (d2(i) == d2(j))
                if (d1(i) != d1(j) && p[i][j] != 2)
                    return false;
        }

    for (int i = 0;i < n;++i) {
        auto &C = c2[i];
        for (int &u : C) u = d1(u);
        sort(C.begin(), C.end());
        C.resize(unique(C.begin(), C.end()) - C.begin());
        if (c2[i].size() == 2) return false;
        if (c2[i].size() > 2) {
            int lst = c2[i].back();
            for (int u : c2[i]) {
                edge[u][lst] = edge[lst][u] = true;
                lst = u;
            }
        }
    }
    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);
        for (int j = i+1;j < n;++j)
            ++cnt[ p[i][j] ];
	}
    if (cnt[3] || !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:113:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  113 |     if (cnt[3] || !build_ok(answer))
      |     ^~
supertrees.cpp:115:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  115 |  build(answer);
      |  ^~~~~

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