Submission #1283270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283270		edo	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	104 ms	22180 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

#if defined(LOCAL) && __has_include("../../debug.h")
  #include "../../debug.h"
#elif defined(LOCAL) && __has_include("../debug.h")
  #include "../debug.h"
#elif defined(LOCAL) && __has_include("debug.h")
  #include "debug.h"
#else
  #define debug(...) ((void)0)
#endif

// void build(vc<vc<int>> ans) {
//     int i = 1, j = 1;
//     trav(x, ans) {
//         j = 1;
//         trav(y, x) {
//             if(y) {
//                 pt(i, " ", j, "\n");
//             }
//             ++j;
//         }
//         ++i;
//     }
// }

int construct(vc<vc<int>> p) {
    // debug(p);
	int N = sz(p);
	vc<vc<int>> ans(N, vc<int>(N, 0));

    FOR(N) {
        trav(x, p.at(i)) 
            if(x == 3)
                return 0;
    }
    // debug("Proso");
    FOR(N) {
        if(p.at(i).at(i) != 1) 
            return 0;
        
        FOR(j, N) 
            if(p.at(i).at(j) != p.at(j).at(i))
                return 0;
        
    }

    // debug("Proso");
    vc<char> vis(N, 0);
    vc<vc<int>> comps;
    FOR(N) {
        if(!vis.at(i)) {
            stack<int> st;
            vc<int> comp;
            st.push(i);
            vis.at(i) = 1;
            comp.eb(i);
            while(!st.empty()) {
                int u = st.top();
                st.pop();
                FOR(v, N) {
                    if(!vis.at(v) && p.at(u).at(v) > 0) {
                        vis.at(v) = 1;
                        comp.eb(v);
                        st.push(v);
                    }
                }
            }
            comps.pb(comp);
        }
    }

    trav(comp, comps) {
        vc<int> id(N, -1);
        vc<vc<int>> cls;

        trav(i, comp) {
            if(id[i] == -1) {
                vc<int> ncls = {i};
                id.at(i) = sz(cls);
                trav(j, comp) {
                    if(id.at(j) == -1 && p.at(i).at(j) == 1) {
                        ncls.pb(j);
                        id.at(j) = sz(cls);
                    }
                }
            cls.pb(ncls);
            }
        }

        trav(i, comp) {
            trav(j, comp) {
                if(id.at(i) == id.at(j)) {
                    if(p.at(i).at(j) != 1) 
                        return 0;
                }
                else {
                    if(p.at(i).at(j) != 2)
                        return 0;
                }
            }
        }
        int k = sz(cls);
        if(k == 1) {
            vc<int> ncls = *cls.begin();
            int root = *ncls.begin();
            trav(node, ncls) {
                if(node != root) 
                    ans.at(root).at(node) = ans.at(node).at(root) =1;
            }
        }
        else if(k == 2)
            return 0;
        else {
            vc<int> reps(k);
            FOR(k) 
                reps.at(i) = cls.at(i).at(0);
            
            FOR(k) {
                int u = reps.at(i);
                int v = reps.at((i + 1) % k);
                ans.at(u).at(v) = ans.at(v).at(u) = 1;
            }

            FOR(k) {
                vc<int> ncls = cls.at(i);
                int root = reps.at(i);
                trav(node, ncls) {
                    if(node != root) {
                        ans.at(root).at(node) = ans.at(node).at(root) = 1;
                    }
                }
            }
        }
    }

    // debug(ans);
    build(ans);
	return 1;
}


// void solve() {
//     vc<vc<int>> niz = {
//         {1, 1, 2, 2},
//         {1, 1, 2, 2},
//         {2, 2, 1, 1},
//         {2, 2, 2, 1}
//     };
    
//     construct(niz);
// }

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int tt = 1;
//     // cin >> tt;
//     while(tt--) {
//         solve();
//     }

//     return 0;
// }

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