Submission #1233711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233711		jsw	Connecting Supertrees (IOI20_supertrees)	C++20	11 / 100	111 ms	26280 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<vector<int>>G;
vector<bool>vis;
vector<ll>comp;
vector<vector<ll>>gr;

void dfs(ll cur, ll node){
  vis[node]=1;
  comp[node]=cur;
  gr[cur].push_back(node);
  for(int i=0;i<G.size();i++){
    if(i==node)continue;
    if(G[node][i] && !vis[i])dfs(cur,i);
  }
}

int construct(vector<vector<int>>p){
 vector<vector<int>>b;
 G=p; ll n=p.size();
 comp.resize(n); vis.resize(n); gr.resize(n);
 for(int i=0;i<n;i++){
   b.push_back({});
   for(int j=0;j<n;j++)b[i].push_back(0);
 }
 ll cur=0;
 for(int i=0;i<n;i++){
   if(vis[i])continue;
   dfs(cur,i); cur++;
 }
 ll k;
 for(int i=0;i<cur;i++){
   k=gr[i][0];
   for(int j=1;j<gr[i].size();j++){
     b[k][j]=1;
     b[j][k]=1;
   }
 }
 
 build(b); 
 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