Submission #304575

#	Time	Username	Problem	Language	Result	Execution time	Memory
304575		peti1234	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	270 ms	26360 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int c=1002;
bool v[c], p;
int n, cnt, ki[c], id[c], si;
vector<vector<int> >sz, sol;
vector<int> kor;
void el(int a, int b) {
    sol[a][b]=1, sol[b][a]=1;
}
void dfs(int a) {
    kor.push_back(a);
    ki[a]=a, v[a]=1, id[a]=cnt;
    for (int i=0; i<n; i++) if (!v[i] && sz[a][i]==1) v[i]=1, ki[i]=a, id[i]=cnt, el(a, i);
    for (int i=0; i<n; i++) if (!v[i] && sz[a][i]==2) dfs(i);
}
int construct(vector<vector<int> > x) {
    n=x.size(), sz=x;
    sol.resize(n);
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) sol[i].push_back(0);
    for (int i=0; i<n; i++) {
        if (!v[i]) dfs(i), cnt++;
        si=kor.size();
        if (si>1) {
            if (si==2) p=1;
            for (int i=1; i<si; i++) el(kor[i-1], kor[i]);
            el(kor[0], kor[si-1]);
        }
        kor.clear();
    }
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
        if (ki[i]==ki[j] && sz[i][j]!=1) p=1;
        if (id[i]==id[j] && ki[i]!=ki[j] && sz[i][j]!=2) p=1;
        if (id[i]!=id[j]&& sz[i][j]) p=1;
    }
    if (p) return 0;
    else build(sol);
    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