Submission #404826

#	Time	Username	Problem	Language	Result	Execution time	Memory
404826		AmineTrabelsi	슈퍼트리 잇기 (IOI20_supertrees)	C++14	75 / 100	288 ms	26108 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
    int n;
    vector<int> parent,sz;
    DSU(int _n){
        n = _n;
        for(int i=0;i<=n;i++){
            parent.push_back(i);
            sz.push_back(1);
        }
    }
    int find(int x){
        return parent[x] = (parent[x] == x ? x : find(parent[x]));
    }
    void unite(int a,int b){
        a = find(a);
        b = find(b);
        if(a != b){
            if(sz[a] >= sz[b]){
                parent[b] = a;
                sz[a] += sz[b];
            }else{
                parent[a] = b;
                sz[b] += sz[a];
            }
        }
    }
};
int construct_1(vector<vector<int>> p) {
    // 21
    int n = p.size();
    vector<vector<int>> answer(n,vector<int>(n,0));
    DSU comp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] >= 2)return 0;
            if(p[i][j] == 1)comp.unite(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
        }
    }
    vector<bool> vis(n,0);
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        vis[i] = 1;
        for(int j=0;j<n;j++){
            if(vis[j])continue;
            if(comp.find(i) == comp.find(j)){
                answer[i][j] = answer[j][i] = 1;
                vis[j] = 1;
            }
        }
    }
    build(answer);
    return 1;
}
int construct_2(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n,vector<int>(n,0));
    DSU comp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 3 || p[i][j] == 1)return 0;
            if(p[i][j] == 2)comp.unite(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
        }
    }
    vector<bool> vis(n,0);
    map<int,vector<int>> comps;
    for(int i=0;i<n;i++){
        comps[comp.find(i)].push_back(i);
    }
    for(auto i:comps){
        vector<int> &p = i.second;
        if((int)p.size() == 2)return 0;
        if((int)p.size() < 2)continue;
        for(int i=1;i<(int)p.size();i++){
            answer[p[i]][p[i-1]] = answer[p[i-1]][p[i]] = 1;
        }
        answer[p[(int)p.size()-1]][p[0]] = answer[p[0]][p[(int)p.size()-1]] = 1;
    }
	build(answer);
	return 1;
}
int construct_3(vector<vector<int>> p) {
    //answer exists
    int n = p.size();
    vector<vector<int>> answer(n,vector<int>(n,0));
    DSU comp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 3)return 0;
            if(p[i][j] == 1)comp.unite(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
        }
    }
    vector<bool> vis(n,0);
    vector<bool> is_root(n,0);
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        vis[i] = 1;
        is_root[i] = 1;
        for(int j=0;j<n;j++){
            if(vis[j])continue;
            if(comp.find(i) == comp.find(j)){
                answer[i][j] = answer[j][i] = 1;
                vis[j] = 1;
            }
        }
    }
    DSU nxt(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 2)nxt.unite(i,j);
        }
    }
    map<int,vector<int>> comps;
    for(int i=0;i<n;i++){
        if(is_root[i])comps[nxt.find(i)].push_back(i);
    }
    for(auto i:comps){
        vector<int> &p = i.second;
        if((int)p.size() == 2)return 0;
        if((int)p.size() < 2)continue;
        for(int i=1;i<(int)p.size();i++){
            answer[p[i]][p[i-1]] = answer[p[i-1]][p[i]] = 1;
        }
        answer[p[(int)p.size()-1]][p[0]] = answer[p[0]][p[(int)p.size()-1]] = 1;
    }
    build(answer);
    return 1;
}

int construct(vector<vector<int>> p) {
    int n = p.size();
    bool one = 1,two = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 2)one = 0;
            if(p[i][j] == 1)two = 0;
        }
    }
    if(one)return construct_1(p);
    else if(two)return construct_2(p);
    return construct_3(p);
}

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