Submission #302179

#	Time	Username	Problem	Language	Result	Execution time	Memory
302179		whaleee	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	256 ms	22264 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n);
	forn(i,n) {
		vi empty(n,0);
		answer[i]= empty;
	}
	
	vector<set<int>> clusters;
	vi class_type(n,-1);
	vi cluster_vec(n,-1);
	int cnt = 0;
	forn(i, n) {
		int cnt0 = 0;
		int cnt1 = 0;
		int cnt2 = 0;
		int cnt3 = 0;

		if (cluster_vec[i] == -1) {
			cluster_vec[i] = cnt;
			cnt++;
		}
		int cluster_id = cluster_vec[i];

		forn(j,n) {
			if (p[i][j] == 0) {
				cnt0++;
			}
			else if (p[i][j] == 1) {
				cnt1++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
			}
			else if (p[i][j] == 2) {
				cnt2++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
			}
			else if (p[i][j] == 3) {
				cnt3++;
				if (cluster_vec[j] == -1) {cluster_vec[j] = cluster_id;}
				else if (cluster_vec[j] != cluster_id) {return 0;} // contr
				
			}
            else {assert(0);}
		}

		if (cnt1 == 1 && cnt0 == n-1) {
			class_type[i] = 0;
		}
		else if (cnt1 > 1) {
            forn(j,i) {
                if (cluster_vec[j] == cluster_id  && p[i][j] < 1) {
                    return 0;
                }
            }
			class_type[i] = 1;
		}
		else if (cnt1 == 1 && cnt2 > 0) {
            forn(j,i) {
                if (cluster_vec[j] == cluster_id && p[i][j] < 2) {
                    return 0;
                }
            }
			class_type[i] = 2;
		}
		else if (cnt1 == 1 && cnt2 == 0 && cnt3>0) {
            forn(j,i) {
                if (cluster_vec[j] == cluster_id &&  p[i][j] < 3) {
                    return 0;
                }
            }
			class_type[i] = 3;
		}
	}

	forn(i,cnt) {
		vi cl1;
		vi cl2;
		vi cl3;
		forn(j, n) {
			if (cluster_vec[j] == i) {
				if (class_type[j] == 1) {
					cl1.pb(j);
				}
				else if(class_type[j] == 2) {
					cl2.pb(j);
				}
				else if (class_type[j] == 3) {
					cl3.pb(j);  // WHAT IF 0?
				}
			}
		}
		if (cl1.size() == 0 && cl2.size() == 0 && cl3.size() == 0) {
			continue;
		} 

		forn(j,cl1.size()-1) {  // Connect ones
			answer[cl1[j]][cl1[j+1]] = 1;
			answer[cl1[j+1]][cl1[j]] = 1;
		}
        forn(j,cl2.size()-1) {  // Connect twos
			answer[cl2[j]][cl2[j+1]] = 1;
			answer[cl2[j+1]][cl2[j]] = 1;
		}

        forn(j,cl3.size()-1) {  // Connect threes
			answer[cl3[j]][cl3[j+1]] = 1;
			answer[cl3[j+1]][cl3[j]] = 1;
		}

        if (cl1.size() > 0 && cl2.size() == 0 && cl3.size() == 0) {
            // all ok  
        }
        else if (cl1.size() == 0 && cl2.size() > 2 && cl3.size() == 0) {
            // only twos -> encircle
            answer[cl2.front()][cl2.back()] = 1;
            answer[cl2.back()][cl2.front()] = 1;
        }
        else if (cl1.size() == 0 && cl2.size() == 0 && cl3.size() > 3) {
            answer[cl3.front()][cl3.back()] = 1;
            answer[cl3.back()][cl3.front()] = 1;
            answer[cl3[1]][cl3.back()] = 1;
            answer[cl3.back()][cl3[1]] = 1;
        }
        // 1 -> 2
        else if (cl1.size() > 0 && cl2.size() >= 2) {
            answer[cl1.back()][cl2.back()] = 1;
            answer[cl2.back()][cl1.back()] = 1;
            answer[cl1.back()][cl2.front()] = 1;
            answer[cl2.front()][cl1.back()] = 1;
            // 2-> 3
            if (cl2.size() >=2  && cl3.size() >= 3) {
                answer[cl2.back()][cl3.back()] = 1;
                answer[cl3.back()][cl2.back()] = 1;
                answer[cl2.back()][cl3.front()] = 1;
                answer[cl3.front()][cl2.back()] = 1;
                answer[cl3.front()][cl3.back()] = 1; // encircle three
                answer[cl3.back()][cl3.front()] = 1;
            }
            
        }
        // 1 -> 3
        else if (cl1.size() > 0 && cl3.size() >= 3) {
            answer[cl1.back()][cl3.back()] = 1;
            answer[cl3.back()][cl1.back()] = 1;
            answer[cl1.back()][cl3.front()] = 1;
            answer[cl3.front()][cl1.back()] = 1;
            answer[cl3.front()][cl3.back()] = 1; // encircle three
            answer[cl3.back()][cl3.front()] = 1;
        }
        // 2->3
        else if (cl2.size() >= 3  && cl3.size() >= 3) {
            answer[cl2.back()][cl2.front()] = 1;
            answer[cl2.front()][cl2.back()] = 1; // encircle two
            answer[cl2.back()][cl3.back()] = 1;
            answer[cl3.back()][cl2.back()] = 1;
            answer[cl2.back()][cl3.front()] = 1;
            answer[cl3.front()][cl2.back()] = 1;
        }
        else {
            return 0;
        }
    }

	build(answer);
	return 1;
}

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