Submission #1213634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213634		hengliao	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	155 ms	62216 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=1005;

    ll n;
    ll timer1, timer2;
    vll adj1[mxN];
    vll adj2[mxN];
    bool visited[mxN];

    vll v1[mxN], v2[mxN];
    ll id1[mxN], id2[mxN];

    ll ans[mxN][mxN];

    void dfs1(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        id1[cur]=timer1;
        // v1[id1[cur]].pb(cur);
        for(auto &it:adj1[cur]){
            dfs1(it);
        }
    }


    void dfs2(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        id2[cur]=timer2;
        v2[id2[cur]].pb(cur);
        for(auto &it:adj2[cur]){
            dfs2(it);
        }
    }

    void add_edge(ll a, ll b){
        ans[a][b]=1;
        ans[b][a]=1;
    }
}

int construct(vector<vector<int>> p) {
	n = p.size();
    memset(ans, 0, sizeof(ans));
	for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            if(i==j) continue;
            if(p[i][j]>0){
                adj1[i].pb(j);
                adj1[j].pb(i);
            }
            if(p[i][j]==1){
                adj2[i].pb(j);
                adj2[j].pb(i);
            }   
        }
    }
    memset(visited, 0, sizeof(visited));
    timer1=0;
    for(ll i=0;i<n;i++){
        if(!visited[i]){
            dfs1(i);
            timer1++;
        }
    }
    memset(visited, 0, sizeof(visited));
    timer2=0;
    for(ll i=0;i<n;i++){
        if(!visited[i]){
            dfs2(i);
            timer2++;
        }
    }

    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            if(i==j) continue;
            if(p[i][j]==3) return 0;
            else if(p[i][j]==0){
                if(id1[i]==id1[j]) return 0;
            }
            else if(p[i][j]==2){
                if(id2[i]==id2[j]) return 0;
            }
            else if(p[i][j]==1){
                if(id2[i]!=id2[j]) return 0;
            }
        }
    }

    for(ll i=0;i<timer2;i++){
        v1[id1[v2[i][0]]].pb(v2[i][0]);
        for(ll j=1;j<(ll) v2[i].size();j++){
            add_edge(v2[i][0], v2[i][j]);
        }
    }
    for(ll i=0;i<timer1;i++){
        if((ll) v1[i].size()==1LL) continue;
        if((ll) v1[i].size()==2LL) return 0;
        for(ll j=0;j<(ll) v1[i].size();j++){
            add_edge(v1[i][j], v1[i][(j+1)%((ll) v1[i].size())]);
        }
    }

    vector<vector<int>> re(n, vector<int>(n));
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            re[i][j]=(int) ans[i][j];
        }
    }

    build(re);

	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