Submission #1236569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236569		Petrix	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	119 ms	26224 KiB

supertrees

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

int v[1002],p,n,cnt,s,k[1002],ind[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(i=1;i<s;i++)
                atr(q[i-1],q[i]);
            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: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4