Submission #610853

#	Time	Username	Problem	Language	Result	Execution time	Memory
610853		nohaxjustsoflo	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	222 ms	22172 KiB

supertrees

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1001;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const int inf=1e9;
const int K=600;
struct DSU
{
    vector<int> size,p;
    int comp;
    void build(int n)
    {
        size=vector<int>(n,1);
        p=vector<int>(n);
        iota(p.begin(),p.end(),0);
        comp=n;
    }
    int get(int x)
    {
        if(p[x]^x) p[x]=get(p[x]);
        return p[x];
    }
    bool unite(int a, int b)
    {
        a=get(a),b=get(b);
        if(a==b) return 0;
        if(size[a]>size[b]) swap(a,b);
        p[a]=b;
        size[b]+=size[a];
        comp--;
        return 1;
    }
};
vector<int> who[mxN];
void build(vector<vector<int>> b);
int construct(vector<vector<int>> p)
{
	int n=p.size();
	DSU dsu; dsu.build(n);
	for(int j=0; j<n; j++) for(int i=j+1; i<n; i++)
    {
        if(p[j][i]==3) return 0;
        if(p[j][i]) dsu.unite(j,i);
    }
	for(int i=0; i<n; i++) who[dsu.get(i)].push_back(i);
	vector<vector<int>> answ(n,vector<int>(n,0));
	for(int o=0; o<n; o++)
    {
        if(dsu.get(o)==o)
        {
            vector<int> a=who[o];
            bool ok=1,has2=0;
            for(int i:a) for(int j:a)
            {
                if(!p[i][j]) ok=0;
                else if(p[i][j]==2) has2=1;
            }
            if(!ok) return 0;
            if(!has2)
            {
                int i=a[0];
                for(int j:a) if(i^j) answ[i][j]=answ[j][i]=1;
                continue;
            }
            map<vector<int>, vector<int>> mp;
            int v=2;
            vector<int> zasebni;
            for(int i:a)
            {
                vector<int> b;
                for(int j:a) b.push_back(p[i][j]);
                if(b!=vector<int>(a.size(),v)) mp[b].push_back(i);
                else zasebni.push_back(i);
            }
            if(zasebni.size()+mp.size()<=v) return 0;
            for(auto& par:mp)
            {
                int i=par.second[0];
                zasebni.push_back(i);
                for(int j:par.second) if(i^j) answ[i][j]=answ[j][i]=1;
            }
            for(int i=0; i<zasebni.size(); i++)
            {
                int j=i+1;
                if(j==zasebni.size()) j=0;
                int l=zasebni[i], r=zasebni[j];
                answ[l][r]=answ[r][l]=1;
            }
        }
    }
    build(answ);
	return 1;
}

/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);


}

*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:88:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |             if(zasebni.size()+mp.size()<=v) return 0;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~^~~
supertrees.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int i=0; i<zasebni.size(); i++)
      |                          ~^~~~~~~~~~~~~~~
supertrees.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 if(j==zasebni.size()) j=0;
      |                    ~^~~~~~~~~~~~~~~~

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