Submission #697333

#	Time	Username	Problem	Language	Result	Execution time	Memory
697333		Sunbae	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	231 ms	34156 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int>parent, Size;
vector<pair<int,int>> two, zero;
int findUpar(int node){
    if(node == parent[node]) return node;
    return parent[node] = findUpar(parent[node]);
}
void Union(int u, int v){
    int pu = findUpar(u), pv = findUpar(v);
    if(pu == pv) return;
    if(Size[pu] > Size[pv]){
        parent[pv] = pu; Size[pu] += Size[pv];
    }else{
        parent[pu] = pv; Size[pv] += Size[pu];
    }
}
int construct(vector<vector<int>>p){
    int n = p.size(); parent.resize(n); Size.resize(n);
    for(int i = 0; i<n; ++i){
        parent[i] = i; Size[i] = 1;
    }
    for(int i = 0; i<n; ++i){
        for(int j = 0; j<n; ++j){
            if(p[i][j] == 0){
                zero.push_back({i, j});
            }else if(p[i][j] == 1){
                Union(i, j);
            }else if(p[i][j] == 2){
                two.push_back({i, j});
            }else if(p[i][j] == 3){
                return 0;
            }
        }
    }
    vector<vector<int>>adj(n, vector<int>(n, 0));
    ///mark 1
    for(int i = 0; i<n; i++){
        int pi = findUpar(i);
        if(pi != i){
            adj[i][pi] = 1; adj[pi][i] = 1;
        }
    }
    ///check two check one
    for(pair<int,int> it: two){
        int pu = findUpar(it.first), pv = findUpar(it.second);
        if(pu == pv) return 0;
    }
    ///make cycle
    bool emp = two.empty();
    if(!emp){
        vector<int>nodes;
        for(pair<int,int> it: two){
            int pu = findUpar(it.first), pv = findUpar(it.second);
            nodes.push_back(pu); nodes.push_back(pv);
            Union(pu, pv);
        }
        sort(nodes.begin(), nodes.end());
        nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
        int sz = nodes.size();
        if(sz <= 2){
            return 0;
        }
        for(int i = 1; i<=sz-1; ++i){
            adj[nodes[i]][nodes[i-1]] = 1; adj[nodes[i-1]][nodes[i]] = 1;
        }
        adj[nodes[0]][nodes[sz-1]] = 1; adj[nodes[sz-1]][nodes[0]] = 1;
    }
    ///check 0
    for(pair<int,int> it: zero){
        if(findUpar(it.first) == findUpar(it.second)) return 0;
    }
    build(adj); return 1;
}

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