Submission #1203935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203935		dpsaveslives	슈퍼트리 잇기 (IOI20_supertrees)	C++20	11 / 100	115 ms	26052 KiB

supertrees

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

int P[1005][1005];
bool vis[1005];
int mx,N;
vector<int> comp,cyc;
vector<int> tree;
vector<bool> vis2;
void dfs(int u, int p){
    vis[u] = 1; comp.push_back(u);
    for(int i = 0;i<N;++i){
        mx = max(mx,P[u][i]);
        if(!vis[i] && P[u][i] > 0){
            dfs(i,u);
        }
    }
}
void dfs2(int u, int p){
    vis2[u] = 1; tree.push_back(u);
    for(auto v : comp){
        if(!vis2[v] && P[u][v] == 1){
            dfs2(v,u);
        }
    }
}
int construct(vector<vector<int>> p){
    memset(vis,false,sizeof(vis));
    N = p.size();
    vector<vector<int>> ans(N,vector<int>(N,0));
    for(int i = 0;i<N;++i){
        for(int j = 0;j<N;++j){
            P[i][j] = p[i][j];
        }
    }
    for(int i = 0;i<N;++i){
        if(!vis[i]){
            mx = -1;
            dfs(i,-1);
            if(mx == 3) return 0;
            for(int j = 0;j<comp.size();++j){
                for(int k = 0;k<j;++k){
                    if(P[comp[j]][comp[k]] == 0){
                        return 0;
                    }
                }
            }
            if(mx == 1){
                for(int j = 1;j<comp.size();++j){
                    ans[comp[j-1]][comp[j]] = ans[comp[j]][comp[j-1]] = 1;
                }
                //build(ans);
                /*for(int j = 0;j<ans.size();++j){
                    for(int k = 0;k<ans.size();++k){
                        cout << ans[j][k] << " ";
                    }
                    cout << "\n";
                }*/
                continue;
            }
            //mx = 2
            vis2 = vector<bool>(N,false); cyc.clear();
            for(int j = 0;j<comp.size();++j){
                if(!vis2[comp[j]]){
                    tree.clear();
                    dfs2(comp[j],-1);
                    for(int k = 0;k<tree.size();++k){
                        for(int l = 0;l<k;++l){
                            if(P[tree[k]][tree[l]] != 1) return 0;
                        }
                        ans[tree[0]][tree[k]] = ans[tree[k]][tree[0]] = 1;
                    }
                    cyc.push_back(tree[0]);
                }
            }
            if(cyc.size() <= 2) return 0;
            for(int j = 1;j<cyc.size();++j){
                ans[cyc[j-1]][cyc[j]] = ans[cyc[j]][cyc[j-1]] = 1;
            }
            ans[cyc.back()][cyc[0]] = ans[cyc[0]][cyc.back()] = 1;
            //build(ans);
            /*for(int j = 0;j<ans.size();++j){
                for(int k = 0;k<ans.size();++k){
                    cout << ans[j][k] << " ";
                }
                cout << "\n";
            }*/

        }
    }
    build(ans);
    return 1;

}

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