Submission #521245

#	Time	Username	Problem	Language	Result	Execution time	Memory
521245		oneloveforever	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	188 ms	22020 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
struct DSU
{
    int n;
    vector<int>trace;
    DSU(int _n=0)
    {
        n=_n;
        trace.resize(n+7);
        iota(trace.begin(),trace.end(),0);
    }
    int get(int x)
    {
        return trace[x]==x?trace[x]:trace[x]=get(trace[x]);
    }
    void connect(int x,int y)
    {
        int u=get(x);
        int v=get(y);
        if(u==v)return ;
        trace[v]=u;
    }
};
int construct(vector<vector<int> >p)
{
    int n=p.size();
    DSU only(n);
    DSU can(n);
    for(int i=0;i<=n-1;i++)
    {
        for(int j=0;j<=n-1;j++)if(p[i][j]==3)return 0;
    }
    vector<vector<int> >b(n,vector<int>(n));
    for(int i=0;i<=n-1;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            if(p[i][j]==1)only.connect(i,j);
            if(p[i][j])can.connect(i,j);
        }
    }
    for(int i=0;i<=n-1;i++)
    {
        if(can.get(i)!=i)continue;
        vector<int>q;
        for(int node=0;node<=n-1;node++)
        {
            if(can.get(node)==i&&only.get(node)==node)q.push_back(node);
        }
        if((int)q.size()==1)continue;
        if((int)q.size()==2)return 0;
        for(int node=0;node<=q.size()-2;node++)
        {
            int node_x=q[node];
            int node_y=q[(node+1)%(int)q.size()];
            b[node_x][node_y]=1;
            b[node_y][node_x]=1;
        }
    }
    for(int i=0;i<=n-1;i++)if(only.get(i)!=i)
    {
        int node=only.get(i);
        b[node][i]=b[i][node]=1;
    }
    for(int i=0;i<=n-1;i++)
    {
        for(int j=i+1;j<=n-1;j++)
        {
            if(only.get(i)==only.get(j))
            {
                //cout<<i<<" "<<j<<" "<<p[i][j]<<endl;
                if(p[i][j]!=1)return false;
            }
            else if(can.get(i)==can.get(j))
            {
                if(p[i][j]!=2)return false;
            }
            else
            {
                if(p[i][j])return false;
            }
        }
    }
    build(b);
    return 1;


}

Compilation message (stderr)

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

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