Submission #849600

#	Time	Username	Problem	Language	Result	Execution time	Memory
849600		abcvuitunggio	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	194 ms	24144 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n,l[1001];
vector <int> v,ve[1001];
vector <vector <int>> g;
int f(int u){
    return (l[u]<0?u:l[u]=f(l[u]));
}
bool unite(int u, int v){
    u=f(u);
    v=f(v);
    if (u==v)
        return false;
    if (l[u]<l[v])
        swap(u,v);
    l[u]+=l[v];
    l[v]=u;
    return true;
}
int construct(vector <vector <int>> p){
    n=p.size();
    g.resize(n);
    for (int i=0;i<n;i++)
        g[i].resize(n);
    memset(l,-1,sizeof(l));
	for (auto i:p)
        for (int j:i)
            if (j==3)
                return 0;
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
            if (p[i][j]==1)
                g[i][j]=g[j][i]=unite(i,j);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (f(i)==f(j)&&p[i][j]!=1)
                return 0;
    for (int i=0;i<n;i++)
        if (f(i)==i)
            v.push_back(i);
    memset(l,-1,sizeof(l));
    for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
            if (p[i][j]==2)
                unite(i,j);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            if (f(i)==f(j)&&!p[i][j])
                return 0;
    for (int i:v)
        ve[f(i)].push_back(i);
    for (int i=0;i<n;i++){
        if (ve[i].size()<=1)
            continue;
        if (ve[i].size()==2)
            return 0;
        for (int j=0;j<ve[i].size();j++){
            int u=ve[i][j],v=ve[i][(j+1)%ve[i].size()];
            g[u][v]=g[v][u]=1;
        }
    }
    build(g);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int j=0;j<ve[i].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