Submission #747150

#	Time	Username	Problem	Language	Result	Execution time	Memory
747150		Rafi22	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	214 ms	28040 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=1007;

/*void build(vector<vector<int>>r)
{
    int n=sz(r);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++) cout<<r[i][j]<<" ";
        cout<<endl;
    }
}*/

bool odw[N];
int odw1[N];
vector<int>V,V1;
int G[N][N];
int n,c;
bool ok=1;

void dfs(int v)
{
    odw[v]=1;
    for(auto u:V) if(G[v][u]==0) ok=0;
    V.pb(v);
    for(int i=0;i<n;i++) if(G[v][i]>0&&!odw[i]) dfs(i);
}

void dfs1(int v)
{
    odw1[v]=c;
    for(auto u:V1) if(G[v][u]!=1) ok=0;
    V1.pb(v);
    for(int i=0;i<n;i++) if(G[v][i]==1&&!odw1[i]) dfs1(i);
}

int construct(vector<vector<int>>p)
{
    n=sz(p);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) G[i][j]=p[i][j];
    vector<vector<int>>b(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
    {
        if(odw[i]) continue;
        V.clear();
        dfs(i);
        memset(odw1,0,sizeof odw1);
        vector<int>cycle;
        for(auto v:V)
        {
            if(odw1[v]) continue;
            cycle.pb(v);
            c++;
            V1.clear();
            dfs1(v);
            for(int i=1;i<sz(V1);i++)
            {
                b[V1[i]][V1[i-1]]=1;
                b[V1[i-1]][V1[i]]=1;
            }
        }
        for(auto a:V)
        {
            for(auto b:V)
            {
                if(odw1[b]!=odw1[a]&&G[a][b]!=2) ok=0;
                if(odw1[b]==odw1[a]&&G[a][b]!=1) ok=0;
            }
        }
        if(sz(cycle)>2)
        {
            for(int i=0;i<sz(cycle);i++)
            {
                b[cycle[i]][cycle[(i+1)%sz(cycle)]]=1;
                b[cycle[(i+1)%sz(cycle)]][cycle[i]]=1;
            }
        }
        if(sz(cycle)==2) ok=0;
    }
    if(!ok) return 0;
    build(b);
    return 1;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
    return 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