Submission #1230510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230510		Hamed_Ghaffari	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	123 ms	26204 KiB

supertrees

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

const int MXN = 1003;

int n;
vector<vector<int>> p, b;
vector<int> V;
int mark[MXN];

void dfs1(int v) {
    mark[v] = 1;
    V.push_back(v);
    for(int u=0; u<n; u++)
        if(p[v][u] && !mark[u])
            dfs1(u);
}

vector<int> V2;

void dfs2(int v) {
    mark[v] = 2;
    V2.push_back(v);
    for(int u=0; u<n; u++)
        if(p[v][u]==1 && mark[u]==1)
            dfs2(u);
}

bool solve() {
    for(int v : V)
        for(int u : V)
            if(p[v][u]==0)
                return 0;
    vector<int> vec;
    for(int v : V)
        if(mark[v]==1) {
            V2.clear();
            dfs2(v);
            for(int i : V2)
                for(int j : V2)
                    if(p[i][j]==2)
                        return 0;
            vec.push_back(v);
            for(int i=0; i+1<V2.size(); i++)
                b[V2[i]][V2[i+1]] = b[V2[i+1]][V2[i]] = 1;
        }
    if(vec.size()==1) return 1;
    if(vec.size()==2) return 0;
    for(int i=0; i+1<vec.size(); i++)
        b[vec[i]][vec[i+1]] = b[vec[i+1]][vec[i]] = 1;
    b[vec[0]][vec.back()] = b[vec.back()][vec[0]] = 1;
    return 1;
}

int construct(vector<vector<int>> p) {
    ::p = p;
    n = p.size();
    b = vector<vector<int>>(n, vector<int>(n, 0));
    for(auto &i: p)
        for(int j : i)
            if(j==3)
                return 0;
    for(int v=0; v<n; v++)
        if(!mark[v]) {
            V.clear();
            dfs1(v);
            if(!solve()) return 0;
        }
    build(b);
    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