Submission #1312981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312981		coderg	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	114 ms	22200 KiB

supertrees

#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
#define F(i,l,r) for(int i=(l);i<(r);++i)
#define FR(i,l,r) for(int i=(l);i>=(r);--i)
typedef long long ll;

const int maxn=(1<<20);
const int mod=1e9+7;
const int mox=2000*500+505;
const int inf=1e9;

struct DSU{
    vector<int> par;
    DSU(int n){
        par.resize(n);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        if(par[x]==x)return x;
        return par[x]=find(par[x]);
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x!=y)par[x]=y;
    }
};

int construct(vector<vector<int>> p){
    int n=p.size();
    vector<vector<int> > b(n,vector<int>(n,0));
    F(i,0,n){
        F(j,0,n)if(p[i][j]==3)return 0;
    }
    DSU uf1(n);
    F(i,0,n){
        F(j,0,n){
            if(p[i][j])uf1.merge(i,j);
        }
    }
    F(i,0,n){
        F(j,0,n){
            if((uf1.find(i)==uf1.find(j))!=(p[i][j]>0))return 0;
        }
    }
    vector<vector<int> > comps(n);
    F(i,0,n)comps[uf1.find(i)].pb(i);
    F(c,0,n){
        if(comps[c].empty())continue;
        const vector<int>& nodes=comps[c];
        DSU uf2(n);
        for(int i:nodes){
            for(int j:nodes){
                if(p[i][j]==1)uf2.merge(i,j);
            }
        }
        vector<int> reps;
        vector<bool> seen(n,0);
        for(int i:nodes){
            int rt=uf2.find(i);
            if(!seen[rt]){
                seen[rt]=1;
                reps.pb(rt);
                vector<int> group;
                for(int j:nodes){
                    if(uf2.find(j)==rt)group.pb(j);
                }
                for(int k=0;k+1<group.size();++k){
                    int u=group[k],v=group[k+1];
                    b[u][v]=b[v][u]=1;
                }
            }
        }
        for(int i:nodes){
            for(int j:nodes){
                if(uf2.find(i)==uf2.find(j)){
                    if(p[i][j]!=1)return 0;
                }else{
                    if(p[i][j]!=2)return 0;
                }
            }
        }
        int m=reps.size();
        if(m==2)return 0;
        if(m>=3){
            F(k,0,m){
                int u=reps[k],v=reps[(k+1)%m];
                b[u][v]=b[v][u]=1;
            }
        }
    }
    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void setIO(std::string)':
supertrees.cpp:11:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:11:98: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void setIO(string name = ""){if(name.size()){ freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}}
      |                                                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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