Submission #1289725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289725		eri16	Connecting Supertrees (IOI20_supertrees)	C++20	11 / 100	95 ms	22540 KiB

supertrees

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


vector <int> visited(1005);
pair<int,vector <int>> fc(int i, vector<vector<int>> &p){
    
    vector <int> tm;    
    int ans=0;
    
    tm.push_back(i);
    
    if (visited[i]==0){
        visited[i]=1;
        for (int j=0; j<p.size(); j++){
            if (p[i][j]==1 && visited[j]==0 && i!=j){
                //tm.push_back(j);
                ans++;
                pair<int,vector <int>> tt;
                tt=fc(j,p);
                ans+=tt.first;
                for (int t=0; t<tt.second.size(); t++){
                    tm.push_back(tt.second[t]);
                }
            }
        }
    }
    
    //cout<<ans<<' ';
    
    return {ans,tm};
}

int construct(vector<vector<int>> p){
    int n=p.size();
    
    vector<vector<int>> arr(n);

    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (p[i][j]!=p[j][i]){return 0;}
            //if (i==j){p[i][i]=0;}
            arr[i].push_back(0);
        }
    }
    
    vector <vector<int>> tree(n);
    for (int i=0; i<n; i++){visited[i]=0;}
    
    
    int k=0;
    for (int i=0; i<n; i++){
        if (visited[i]==0){
            pair<int,vector <int>> tt;
            
            tt=fc(i,p);
            
            //if (tt.first+1!=tt.second.size()){return 0;}
            
            for (int i=0; i<tt.second.size(); i++){
                tree[k].push_back(tt.second[i]);
            }
            k++;
        }
    }    
    
    for (int i=0; i<k; i++){
        for (int j=0; j<tree[i].size()-1; j++){
            arr[tree[i][j]][tree[i][j+1]]=1;
            arr[tree[i][j+1]][tree[i][j]]=1;
        }
    }
    
    build(arr);
    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