Submission #613890

#	Time	Username	Problem	Language	Result	Execution time	Memory
613890		alirezasamimi100	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	221 ms	23508 KiB

supertrees

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

const int N = 1e3 + 10;

int n,P[N];
vector<int> vec[N],cy[N];

int gp(int x){
    return P[x]!=-1?P[x]=gp(P[x]):x;
}

void uni(int v, int u){
    v=gp(v);
    u=gp(u);
    if(v==u) return;
    P[u]=v;
}

int construct(vector<vector<int>> p) {
    memset(P,-1,sizeof P);
    n = p.size();
    vector<vector<int>> ans(n,vector<int>(n,0));
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(p[i][j]==1) uni(i,j);
            if(p[i][j]==3) return 0;
        }
    }
    for(int i=0; i<n; i++) vec[gp(i)].pb(i);
    memset(P,-1,sizeof P);
    for(int i=0; i<n; i++){
        for(int j : vec[i]){
            if(j!=i) ans[i][j]=ans[j][i]=1;
            for(int k : vec[i]) if(p[j][k]!=1) return 0;
        }
        for(int j=0; j<n; j++){
            if(i==j) continue;
            bool f=0,g=0;
            for(int x : vec[i]){
                for(int y : vec[j]){
                    if(p[x][y]==2) f=1;
                    if(p[x][y]==0) g=1;
                }
            }
            if(f && g) return 0;
            if(f) uni(i,j);
        }
    }
    for(int i=0; i<n; i++) if(!vec[i].empty()){
        cy[gp(i)].pb(i);
    }
    for(int i=0; i<n; i++){
        for(int a : cy[i]){
            for(int b : cy[i]){
                if(a==b) continue;
                for(int x : vec[a]){
                    for(int y : vec[b]){
                        if(p[x][y]!=2) return 0;
                    }
                }
            }
        }
        if((int)cy[i].size()==2) return 0;
        if((int)cy[i].size()<3) continue;
        int ls = i;
        for(int j : cy[i]){
            if(j==i) continue;
            ans[ls][j]=ans[j][ls]=1;
            ls=j;
        }
        ans[ls][i]=ans[i][ls]=1;
    }
    build(ans);
    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