Submission #406099

#	Time	Username	Problem	Language	Result	Execution time	Memory
406099		Falcon	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	288 ms	28012 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)

int construct_forest(const vector<vector<int>>& p) {
    int n{int(p.size())};
    vector<bool> vis(n);
    rep(i, n) if(!vis[i])
        rep(j, n)
            if(p[i][j]) {
                if(p[i] != p[j])
                    return 0;
                vis[j] = true;
            }
                
    return 1;
}

vector<vector<int>> build_forest(const vector<vector<int>>& p) {
    int n{int(p.size())};
    vector<bool> vis(n);
    vector<vector<int>> adj(n, vector<int>(n));
    rep(i, n) if(!vis[i]) 
        rep(j, n) if(p[i][j] && i != j) 
            adj[i][j] = adj[j][i] = 1, vis[j] = true;
    return adj;
}


int add_cycles(const vector<vector<int>>& p, vector<vector<int>>& adj) {
    int n{int(p.size())};
    vector<bool> vis(n);
    vector<int> tree_head;
    vector<int> tree_of(n);
    int t{};
    rep(i, n) if(!vis[i]) {
        tree_head.push_back(i);
        rep(j, n) if(p[i][j] == 1)
            tree_of[j] = t, vis[j] = true;
        ++t;
    }

    rep(i, n) rep(j, n)
        if(p[i][j] == 1) assert(tree_of[i] == tree_of[j]);
        else assert(tree_of[i] != tree_of[j]);

    rep(i, n) rep(j, n)
        if(p[i][j] == 2 && p[tree_head[tree_of[i]]][j] != 2)
            return 0;
        else if(p[tree_head[tree_of[i]]][j] == 2 && p[i][j] != 2)
            return 0;

    fill(vis.begin(), vis.end(), false);
    vector<vector<int>> tree_comp;
    for(int i: tree_head) if(!vis[i]) {
        tree_comp.emplace_back();
        for(int j: tree_head) if(p[i][j] != 0) {
            rep(k, n) {
                if(p[i][k] == 2 && p[k][j] == 0)
                    return 0;
                else if(p[i][k] == 0 && p[k][j] == 2)
                    return 0;
                vis[j] = true;
            }
            tree_comp.back().push_back(j);
        }
    }
    
    for(vector<int>& comp: tree_comp) {
        if(int(comp.size()) == 2)
            return 0;
        rep(i, int(comp.size())) {
            int j = comp[(i + 1) % int(comp.size())];
            if(comp[i] != j)
                adj[comp[i]][j] = adj[j][comp[i]] = 1;
        }
    }

    return 1;
}

int construct(vector<vector<int>> p) {
    int n{int(p.size())};
    vector<vector<int>> p2{p};
    rep(i, n) rep(j, n) p2[i][j] %= 2;
    
    if(!construct_forest(p2))
        return 0;

    vector<vector<int>> adj{build_forest(p2)};
    if(!add_cycles(p, adj))
        return 0;
    
    build(adj);
	return 1;
}

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