Submission #411041

#	Time	Username	Problem	Language	Result	Execution time	Memory
411041		phathnv	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	296 KiB

supertrees

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

const int N = 1000;

int nn;
bool vst[N], mark[N];
vector<vector<int>> a;

void Dfs(int u, int val, vector<int> &vexs) {
    if (vst[u])
        return;
    vst[u] = 1;
    vexs.push_back(u);
    for(int v = 0; v < nn; v++)
        if (a[u][v] == val)
            Dfs(v, val, vexs);
}

int construct(vector<vector<int>> p) {
    a = p;
    nn = a.size();
    int maxA = 0;
    for(int i = 0; i < nn; i++)
        for(int j = 0; j < nn; j++)
            maxA = max(maxA, a[i][j]);
    if (maxA == 3)
        return 0;
    vector<vector<int>> res(nn, vector<int>(nn, 0));
    memset(vst, 0, sizeof(vst));
    memset(mark, 0, sizeof(mark));
    for(int i = 0; i < nn; i++)
        for(int j = 0; j < nn; j++)
            if (a[i][j] == 2)
                mark[i] = 1;
    for(int i = 0; i < nn; i++)
        vst[i] = mark[i] ^ 1;
    for(int u = 0; u < nn; u++) {
        if (vst[u])
            continue;
        vector<int> vexs;
        Dfs(u, 1, vexs);
        for(int i = 0; i < (int) vexs.size(); i++)
            for(int j = i + 1; j < (int) vexs.size(); j++)
                if (a[vexs[i]][vexs[j]] != 1)
                    return 0;
        for(int i = 1; i < (int) vexs.size(); i++)
            res[vexs[i - 1]][vexs[i]] = res[vexs[i]][vexs[i - 1]] = 1;
    }
    build(res);
	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