Submission #1029918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029918		happy_node	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	165 ms	24232 KiB

supertrees

#include "supertrees.h"

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

int construct(std::vector<std::vector<int>> p) {
        int N=p.size();

        for(int i=0;i<N;i++) {
                for(int j=0;j<N;j++) {
                        if(p[i][j]==3) return 0;
                }
        }

        vector<vector<int>> comp(N);
        // merge two nodes with number of paths = 1 and everything else equal -> no more 1's    

        vector<bool> vis(N);
        for(int i=0;i<N;i++) {
                if(vis[i]) continue;
                comp[i].push_back(i);
                vis[i]=true;
                for(int j=i+1;j<N;j++) {
                        if(vis[j]) continue;
                        if(p[i][j]!=1) continue;

                        vis[j]=true;
                        comp[i].push_back(j);
                }
        }

        vector<bool> head(N);
        for(int i=0;i<N;i++) {
                if(comp[i].empty()) continue;
                head[i]=true;
                for(auto j:comp[i]) {
                        if(p[j]!=p[i]) return 0;
                }
        }

        // create the cycle with nodes of #paths = 2, you need to check if every node in the path is valid 
        // (has 2 as num of paths to every other node in cycle, 0 to everything else)

        for(int i=0;i<N;i++) {
                p[i][i]=2;
                if(!head[i]) {
                        for(int j=0;j<N;j++) p[i][j]=0, p[j][i]=0;
                }
        }

        vector<vector<int>> cyc(N);
        vector<bool> vis2(N);

        for(int i=0;i<N;i++) {
                if(!head[i] || vis2[i]) continue;
                for(int j=0;j<N;j++) {
                        if(!head[j] || vis2[j]) continue;
                        if(p[i][j]==2) {
                                cyc[i].push_back(j);
                                vis2[j]=true;
                        }
                }
        }

        for(int i=0;i<N;i++) {
                if(cyc[i].empty()) continue;
                for(auto j:cyc[i]) {
                        if(p[j]!=p[i]) return 0;
                }
        }

        vector<vector<int>> ans(N,vector<int>(N));

        for(int i=0;i<N;i++) {
                if(cyc[i].empty()) continue;
                int s=cyc[i].size();
                if(s==1) continue;
                if(s==2) return 0;

                for(int j=0;j<s;j++) {      
                        ans[cyc[i][j]][cyc[i][(j+1)%s]]=1;
                        ans[cyc[i][(j+1)%s]][cyc[i][j]]=1;
                }
        }

        for(int i=0;i<N;i++) {
                if(comp[i].empty()) continue;
                int s=comp[i].size();
                for(int j=0;j+1<s;j++) {      
                        ans[comp[i][j]][comp[i][j+1]]=1;
                        ans[comp[i][j+1]][comp[i][j]]=1;
                }
        }

        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