Submission #800116

#	Time	Username	Problem	Language	Result	Execution time	Memory
800116		PixelCat	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	173 ms	22092 KiB

supertrees

#include "supertrees.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000;
const int BASE = 7;
const int MOD = 998244353;

vector<vector<int>> answer;
inline void add_edge(int a, int b) {
    answer[a][b] = answer[b][a] = 1;
}

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    bool lead(int n) {
        return p[n] < 0;
    }
} dsu;

bool solve_sun(vector<vector<int>> &p, vector<int> &cc) {
    int n = sz(cc);

    // leave p[i][j] = 1 or 2 only
    for(auto &v1:cc) for(auto &v2:cc) if(v1 != v2) {
        if(p[v1][v2] == 0) return false;
    }

    // phase 1: collect groups of tantacles
    vector<pii> vh;  // {hash, index}
    For(i, 0, n - 1) {
        int h = 0;
        For(j, 0, n - 1) {
            h = (h * BASE + p[cc[i]][cc[j]]) % MOD;
        }
        vh.eb(h, cc[i]);
    }
    sort(all(vh));
    vector<vector<int>> g;
    g.eb();
    g.back().eb(vh[0].S);
    For(i, 1, n - 1) {
        if(vh[i].F != vh[i - 1].F) g.eb();
        g.back().eb(vh[i].S);
    }

    // phase 2-1: link cycle
    For(i, 1, sz(g) - 1) {
        add_edge(g[i].back(), g[i - 1].back());
    }
    add_edge(g.front().back(), g.back().back());

    // phase 2-2: link tantacles
    for(auto &i:g) {
        int rt = i.back();
        i.pop_back();
        for(auto &j:i) {
            add_edge(j, rt);
        }
    }

    return true;
}

int construct(vector<vector<int>> p) {
    int n = sz(p);
    For(i, 0, n - 1) For(j, 0, n - 1) if(p[i][j] == 3) return 0;
    answer = vector<vector<int>>(n, vector<int>(n, 0));

    // phase 1: find all CC
    dsu.init();
    For(i, 0, n - 1) For(j, 0, n - 1) {
        if(p[i][j]) dsu.uni(i, j);
    }
    vector<vector<int>> vcc;
    For(i, 0, n - 1) if(dsu.lead(i)) {
        vcc.eb();
        For(j, 0, n - 1) if(dsu.same(i, j)) {
            vcc.back().eb(j);
        }
    }

    // phase 2: solve for each CC
    for(vector<int> &cc:vcc) if(sz(cc) > 1) {
        int mask = 0;
        for(auto &v1:cc) for(auto &v2:cc) if(v1 != v2) {
            mask |= (1 << p[v1][v2]);
        }
        if(mask & 1) return 0;
        if(mask == 2) {
            int rt = cc.back();
            cc.pop_back();
            for(auto &i:cc) {
                add_edge(i, rt);
            }
        } else {
            if(!solve_sun(p, cc)) return 0;
        }
    }

    build(answer);
    return 1;
}

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