Submission #336813

#	Time	Username	Problem	Language	Result	Execution time	Memory
336813		MvC	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	290 ms	24300 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e3+50;
const ll mod=1e9+7;
using namespace std;
int n,i,j,t,p1[nmax],p2[nmax];
vector<vector<int> >b;
vector<int>v1[nmax],v2[nmax],vc;
int fnd1(int x)
{
    if(p1[x]==x)return x;
    return p1[x]=fnd1(p1[x]);
}
void uni1(int x,int y)
{
    x=fnd1(x),y=fnd1(y);
    if(x==y)return;
    p1[x]=y;
}
int fnd2(int x)
{
    if(p2[x]==x)return x;
    return p2[x]=fnd2(p2[x]);
}
void uni2(int x,int y)
{
    x=fnd2(x),y=fnd2(y);
    if(x==y)return;
    p2[x]=y;
}
int construct(vector<vector<int> > r)
{
    n=lun(r);
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==3)return 0;
    for(i=0;i<n;i++)p1[i]=p2[i]=i;
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j])uni1(i,j);
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(!r[i][j] && fnd1(i)==fnd1(j))return 0;
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]==1)uni2(i,j);
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(r[i][j]!=1 && fnd2(i)==fnd2(j))return 0;
    for(i=0;i<n;i++)v1[fnd1(i)].pb(i);
    b.resize(n);
    for(i=0;i<n;i++)b[i].resize(n);
    for(i=0;i<n;i++)
    {
        if(v1[i].empty())continue;
        for(j=0;j<lun(v1[i]);j++)v2[fnd2(v1[i][j])].pb(v1[i][j]);
        vc.clear();
        for(j=0;j<n;j++)
        {
            if(v2[j].empty())continue;
            for(t=0;t<lun(v2[j])-1;t++)
            {
                b[v2[j][t]][v2[j][t+1]]=b[v2[j][t+1]][v2[j][t]]=1;
            }
            vc.pb(j);
            v2[j].clear();
        }
        if(lun(vc)==2)return 0;
        for(j=0;j<lun(vc)-1;j++)b[vc[j]][vc[j+1]]=b[vc[j+1]][vc[j]]=1;
    }
    build(b);
    return 1;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);

    return 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