Submission #428736

#	Time	Username	Problem	Language	Result	Execution time	Memory
428736		Emin2004	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	373 ms	28184 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pii pair <int, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 1005;
const int mod = 1e9 + 7;

int parent[N], rnk[N], ans[N][N], incyc[N], mnmn;
vector<int> component[N];
set<int> s;

int getpar(int a){
    if(parent[a] == a) return a;
    return parent[a] = getpar(parent[a]);
}

void uni(int a, int b){
    if(rnk[a] > rnk[b]) swap(a, b);
    parent[a] = b;
    s.insert(b);
    if(s.find(a) != s.end()) s.erase(s.find(a));
    if(rnk[a] == rnk[b]) rnk[b]++;
}

void DFS(int node, int par, int root){
    component[root].pb(node);
    for(int i = 0; i < mnmn; i++){
        if(i == par || ans[node][i] == 0) continue;
        DFS(i, node, root);
    }
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	mnmn = n;
	for(int i = 0; i < n; i++) {
        rnk[i] = 0;
        parent[i] = i;
        s.insert(i);
	}
	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;
            int x = getpar(i);
            int y = getpar(j);
            if(x == y && p[i][j] == 0) return 0;
            if(x != y && p[i][j] == 1){
                uni(x, y);
                ans[x][y] = 1;
                ans[y][x] = 1;
            }
        }
	}
	for(set<int>::iterator itr = s.begin(); itr != s.end(); itr++){
        DFS(*itr, *itr, *itr);
	}
	for(set<int>::iterator itr = s.begin(); itr != s.end(); itr++){
        vector<int> v;
        int x = *itr;
        for(set<int>::iterator itr2 = s.begin(); itr2 != s.end(); itr2++){
            int y = *itr2;
            if(x == y) continue;
            if(p[x][y] == 2){
                v.pb(y);
                if((incyc[x] == 1) && getpar(x) != getpar(y)) return 0;
            }
        }
        if(v.size() != 0) v.pb(x);
        if(v.size() == 2) return 0;
        if(incyc[x]) continue;
        for(int i : v){
            for(int j : v){
                if(i == j) continue;
                for(int c1 : component[i]){
                    for(int c2 : component[j]) if(p[c1][c2] != 2) return 0;
                }
            }
            incyc[i] = 1;
        }
        int last = x;
        for(int i : v){
            ans[last][i] = 1;
            ans[i][last] = 1;
            last = i;
            parent[i] = x;
        }
	}
	vector<vector<int>> answer(n);
	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            answer[i].pb(ans[i][j]);
        }
	}
	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