Submission #411077

#	Time	Username	Problem	Language	Result	Execution time	Memory
411077		kwongweng	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	289 ms	24036 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second

vi p1(1001), p2(1001), sz1(1001, 1), sz2(1001, 1);
int get1(int a){
    if (p1[a] == a) return a;
    p1[a] = get1(p1[a]);
    return p1[a];
}

void Union1(int a, int b){
    int c = get1(a); int d = get1(b);
    if (c == d) return;
    if (sz1[c] >= sz1[d]){
        p1[d] = c;
        sz1[c] += sz1[d];
    }else{
        p1[c] = d;
        sz1[d] += sz1[c];
    }
}

int get2(int a){
    if (p2[a] == a) return a;
    p2[a] = get2(p2[a]);
    return p2[a];
}
void Union2(int a, int b){
    int c = get2(a); int d = get2(b);
    if (c == d) return;
    if (sz2[c] >= sz2[d]){
        p2[d] = c;
        sz2[c] += sz2[d];
    }else{
        p2[c] = d;
        sz2[d] += sz2[c];
    }
}
int construct(vector<vi> p) {
	int n = p.size();
	FOR(i, 0, n){
	    FOR(j, 0, n){
	        if (p[i][j] == 3) return 0;
	    }
	}
	FOR(i, 0, n){
	    p1[i] = i;
	    p2[i] = i;
	}
	FOR(i, 0, n){
	    FOR(j, 0, n){
	        if (p[i][j] == 1) Union1(i, j);
	    }
	}
	FOR(i, 0, n){
	    FOR(j, 0, n){
	        if (i == get1(i) && j == get1(j)){
	            if (p[i][j] == 2) Union2(i, j);
	        }
	    }
	}
	FOR(i, 0, n){
	    if (sz2[i] == 2) return 0;
	}
	vector<vi> ans;
	FOR(i, 0, n){
	    vi row(n);
	    ans.pb(row);
	}
	FOR(i, 0, n){
	    FOR(j, 0, n){
	        if (p[i][j] == 0){
	            if (get2(get1(i)) == get2(get1(j))) return 0;
	        }
	        if (p[i][j] == 2){
	            if (get1(i) == get1(j) || get2(get1(i)) != get2(get1(j))) return 0;
	        }
	    }
	}
	vi g[n];
	FOR(i, 0, n){
	    ans[get1(i)][i] = 1;
	    ans[i][get1(i)] = 1;
	    if (i == get1(i)){
	        g[get2(i)].pb(i);
	    }
	}
	FOR(i, 0, n){
	    if (get1(i) == i && get2(i) == i){
	        FOR(j, 0, sz2[i]){
	            ans[g[i][j]][g[i][(j+1)%sz2[i]]] = 1;
	            ans[g[i][(j+1)%sz2[i]]][g[i][j]] = 1;
	        }
	    }
	}
	FOR(i, 0, n){
	    ans[i][i] = 0;
	}
	build(ans);
	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