Submission #610837

#	Time	Username	Problem	Language	Result	Execution time	Memory
610837		nohaxjustsoflo	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	185 ms	24076 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]) 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 i=0; i<n; i++)
    {
        if(dsu.get(i)==i)
        {
            vector<int> a=who[i];
            bool ok=1;
            bool has2=0, has3=0;
            for(int i:a) for(int j:a)
            {
                if(!p[i][j]) ok=0;
                else if(p[i][j]==2) has2=1;
                else if(p[i][j]==3) has3=1;
            }
            if(has2&&has3) ok=0;
            if(!ok) return 0;
            if(!has2&&!has3)
            {
                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+has3;
            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)
            {
                if(par.second.size()==1) return 0;
                sort(par.second.begin(),par.second.end());
                int i=par.second[0];
                for(int j:a)
                {
                    auto it=lower_bound(par.second.begin(),par.second.end(),j);
                    if(it!=par.second.end()&&*it==j)
                    {
                        ///nalazi se u ovoj grupi
                        if(p[i][j]!=1) return 0;
                    }
                    else
                    {
                        ///druga grupa
                        if(p[i][j]!=v) return 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;
            }
            if(v==3)
            {
                int l=zasebni[0], r=zasebni[2];
                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:87:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |             if(zasebni.size()+mp.size()<=v) return 0;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~^~~
supertrees.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for(int i=0; i<zasebni.size(); i++)
      |                          ~^~~~~~~~~~~~~~~
supertrees.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if(j==zasebni.size()) j=0;
      |                    ~^~~~~~~~~~~~~~~~

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