Submission #603550

#	Time	Username	Problem	Language	Result	Execution time	Memory
603550		rrrr10000	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	226 ms	22148 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
#include "supertrees.h"
int construct(vector<vector<int>> v){
    ll n=v.size();
    rep(i,n)rep(j,n)if(v[i][j]==3)return 0;
    vi gr1(n,-1);
    ll c1=0;
    rep(i,n)if(gr1[i]==-1){
        queue<ll> que;
        que.push(i);
        gr1[i]=c1;
        while(!que.empty()){
            ll t=que.front();que.pop();
            rep(j,n)if(v[j][t]>0&&gr1[j]==-1){
                gr1[j]=c1;que.push(j);
            }
        }
        c1++;
    }
    rep(i,n)rep(j,i)if(v[i][j]==0&&gr1[i]==gr1[j])return 0;
    rep(i,n)rep(j,i)if(v[i][j]>0&&gr1[i]!=gr1[j])return 0;
    vi gr2(n,-1);
    ll c2=0;
    vvi al1(c1);
    rep(i,n)if(gr2[i]==-1){
        al1[gr1[i]].pb(i);
        queue<ll> que;
        que.push(i);
        gr2[i]=c2;
        while(!que.empty()){
            ll t=que.front();que.pop();
            rep(j,n)if(v[j][t]==1&&gr2[j]==-1){
                gr2[j]=c2;que.push(j);
            }
        }
        c2++;
    }
    vector<vector<int>> ans(n,vector<int>(n));
    vvi al2(c2);
    rep(i,n)al2[gr2[i]].pb(i);
    rep(i,c2)rep(j,al2[i].size()-1){
        ll a=al2[i][j],b=al2[i][j+1];
        ans[a][b]=ans[b][a]=1;
    }
    rep(i,c1)if(al1[i].size()>1){
        if(al1[i].size()==2)return 0;
        rep(j,al1[i].size()){
            ll a=al1[i][j],b=al1[i][(j+1)%al1[i].size()];
            ans[a][b]=ans[b][a]=1;
        }
    }
    rep(i,n)rep(j,i)if(v[i][j]==2&&gr2[i]==gr2[j])return 0;
    rep(i,n)rep(j,i)if(v[i][j]==1&&gr2[i]!=gr2[j])return 0;
    build(ans);
    return 1;
}

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