Submission #1041893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041893		MarwenElarbi	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	128 ms	26200 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define pb push_back
const int nax=1005;
vector<int> adj[nax];
vector<int> comp[nax];
int parent[nax];
int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
    return find(x)==find(y);
}
void joinset(int x,int y){
    x=find(x);
    y=find(y);
    if(comp[y].size()<comp[x].size()) swap(comp[x],comp[y]);
    for(auto u:comp[x]) comp[y].pb(u);
    parent[x]=y;
}
int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    std::vector<std::vector<int>> ans(n,vector<int> (n,0));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(p[i][j]>0) adj[i].pb(j);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
    }
    for (int i = 0; i < n; ++i)
    {
        for(auto u:adj[i])
            if(!sameset(u,i)) joinset(u,i);
    }
    bool test=true;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(p[i][j]==3) test=false;
            if(p[i][j]==0&&sameset(i,j)) test=false;
        }
    }
    if(!test) return test;
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
        adj[i].clear();
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(p[i][j]==1&&!sameset(j,i)){
                adj[i].pb(j);
                adj[j].pb(i);
                joinset(j,i);
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(p[i][j]==2&&sameset(i,j)) test=false;
        }
    }
    if(!test) return test;
    for (int i = 0; i < n; ++i)
    {
        if(comp[find(i)].empty()) comp[find(i)].pb(find(i));
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(i==j) continue;
            if(p[i][j]==2&&!sameset(i,j)){
                joinset(i,j);
            }
        }
    }
    bool vis[n];
    memset(vis,0,sizeof vis);
    for (int i = 0; i < n; ++i)
    {
        if(!vis[find(i)]){
            int x=find(i);
            vis[x]=true;
            if(comp[x].size()==1) continue;
            if(comp[x].size()==2){
                test=false;
                break;
            }
            for (int j = 0; j < comp[x].size(); ++j)
            {
                adj[comp[x][j]].pb(comp[x][(j+1)%(int)comp[x].size()]);
                adj[comp[x][(j+1)%(int)comp[x].size()]].pb(comp[x][j]);
            }
        }
    }
    if(!test) return 0;
    for (int i = 0; i < n; ++i)
    {
        for(auto u:adj[i]) ans[i][u]=1;
    }
    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:106:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for (int j = 0; j < comp[x].size(); ++j)
      |                             ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4