Submission #1165412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165412		TsotneSV	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	119 ms	22272 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=2e5+5; 
const ll inf=1e9,INF=1e18; 

struct DSU {

    vector<int> parent,SIZE;

    DSU(int n) {
        parent.resize(n);
        SIZE.resize(n);
        for(int i=0;i<n;i++) {
            parent[i] = i;
            SIZE[i] = 1;
        }
    }

    int find_set(int u) {
        if(u == parent[u]) return u;
        return parent[u] = find_set(parent[u]);
    }

    void union_sets(int u,int v) {
        u = find_set(u);
        v = find_set(v);

        if(u != v) {
            if(SIZE[u] < SIZE[v]) swap(u,v);
            SIZE[u] += SIZE[v];
            parent[v] = u;
        }
    }

};

int construct(vector<vector<int>> p) {
	int n = p.size(); vector<vector<int>> answer(n,vi(n,0)),A(n),B(n);

    DSU branch(n),necklace(n);

	for (int i = 0; i < n; i++) {

		for(int j = 0; j < n; j++) {

            if(i == j) continue;

            if(p[i][j] == 3) return 0;
            else if(p[i][j] == 1) branch.union_sets(i,j);
            else if(p[i][j] == 2) necklace.union_sets(i,j);

        }

	}

    for(int i=0;i<n;i++) {
        A[branch.find_set(i)].pb(i);
        if(i == branch.find_set(i)) B[necklace.find_set(i)].pb(i);
    }

    for(int i=0;i<n;i++) {
        for(int j=0;j+1<A[i].size();j++) answer[A[i][j]][A[i][j+1]] = answer[A[i][j+1]][A[i][j]] = 1;
        for(int j=0;j+1<B[i].size();j++) answer[B[i][j]][B[i][j+1]] = answer[B[i][j+1]][B[i][j]] = 1;
        if(B[i].size() == 2) return 0;
        if(B[i].size() > 2) answer[B[i].front()][B[i].back()] = answer[B[i].back()][B[i].front()] = 1;
    }

    for(int i = 0; i < n; i++) {

        for(int j = 0; j < n; j++) {

            if(j == i) continue;

            if(p[i][j] != 1 and branch.find_set(i) == branch.find_set(j)) return 0;
            if(p[i][j] == 0 and necklace.find_set(i) == necklace.find_set(j)) return 0;
        
        }

    } 

	build(answer);
	return 1;
}

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