Submission #616693

#	Time	Username	Problem	Language	Result	Execution time	Memory
616693		wiwiho	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	340 KiB

supertrees

#include "supertrees.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int n;
vector<vector<int>> g;
vector<int> vst1, vst2;
vector<vector<int>> cy;
vector<vector<int>> ans;

void dfs1(int now, int id){
    vst1[now] = id;
    for(int i = 0; i < n; i++){
        if(g[now][i] != 1) continue;
        if(vst1[i] != -1) continue;
        ans[now][i] = ans[i][now] = 1;
        dfs1(i, id);
    }
}

void dfs2(int now, int id){
    vst2[now] = id;
    cy[id].eb(vst1[now]);
    for(int i = 0; i < n; i++){
        if(g[now][i] != 1 && g[now][i] != 2) continue;
        if(vst2[i] != -1) continue;
        dfs2(i, id);
    }
}

int construct(vector<vector<int>> p){

	n = p.size();
    g = p;
    vst1.resize(n, -1);
    vst2.resize(n, -1);
    cy.resize(n);
    ans.resize(n, vector<int>(n));

    for(int i = 0; i < n; i++){
        if(vst1[i] != -1) continue;
        dfs1(i, i);
    }

    for(int i = 0; i < n; i++){
        if(vst2[i] != -1) continue;
        dfs2(i, i);
        if(cy[i].size() == 1) continue;
        lsort(cy[i]);
        uni(cy[i]);
        int lst = cy[i].back();
        for(int j : cy[i]){
            ans[lst][j] = ans[j][lst] = 1;
            lst = j;
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int t;
            if(vst1[i] == vst1[j]) t = 1;
            else if(vst2[i] == vst2[j]) t = 2;
            else t = 0;
            if(g[i][j] != t) return 0;
        }
    }

    build(ans);
	return 1;
}

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