Submission #1237812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237812		Petrix	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	122 ms	26236 KiB

supertrees

#include <fstream>
#include <vector>
#include "supertrees.h"
using namespace std;

int n,cnt,s,k[1002],ind[1002];
bool p,v[1002];

vector<vector<int>> mar,rasp;
vector<int> q;

void atr(int a,int b) {
    rasp[a][b]=rasp[b][a]=1;
}

void dfs(int nod){
    int i;
    q.push_back(nod);
    k[nod]=nod;v[nod]=1;ind[nod]=cnt;
    for(i=0;i<n;i++){
        if(!v[i] && mar[nod][i]==1){
            v[i]=1;k[i]=nod;ind[i]=cnt;atr(nod,i);
        }
    }
    for(i=0;i<n;i++){
        if(!v[i] && mar[nod][i]==2) dfs(i);
    }
}
int construct(vector<vector<int>> x){
    int i,j;
    n=x.size();mar=x;
    rasp.resize(n);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            rasp[i].push_back(0);
    }
    for(i=0;i<n;i++) {
        if(!v[i]){
            dfs(i);cnt++;
        }
        s=q.size();
        if(s>1) {
            if(s==2) p=1;
            for(j=1;j<s;j++)
                atr(q[j-1],q[j]);
            atr(q[0],q[s-1]);
        }
        q.clear();
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++) {
            if(k[i]==k[j] && mar[i][j]!=1) p=1;
            if(ind[i]==ind[j] && k[i]!=k[j] && mar[i][j]!=2) p=1;
            if(ind[i]!=ind[j]&& mar[i][j]) p=1;
        }
    }
    if(p) return 0;
    else build(rasp);
    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