Submission #779192

#	Time	Username	Problem	Language	Result	Execution time	Memory
779192		jasmin	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	176 ms	22068 KiB

supertrees

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

/*void build(vector<vector<int> > adi){
        int n=adi.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cout << adi[i][j] << " ";
            }
            cout << "\n";
        }
}*/

vector<vector<int> > components(vector<vector<int> >& p, int n, bool& pos){
    vector<vector<int> > comp;

    vector<bool> vis(n);
    vector<int> comp_num(n, -1); int mom=0;
    for(int v=0; v<n; v++){
        if(vis[v]) continue;
        vis[v]=true;

        comp.push_back({});
        comp.back().push_back(v);
        comp_num[v]=mom;

        for(int u=0; u<n; u++){
            if(u!=v && p[v][u]!=0){

                comp.back().push_back(u);
                comp_num[u]=mom;
                vis[u]=true;
            }
        }
        mom++;
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){

            if(comp_num[i]==comp_num[j]){
                pos = pos && (p[i][j]!=0 && p[j][i]!=0);
            }
            else{
                pos = pos && (p[i][j]==0 && p[j][i]==0);
            }

        }
    }
    
    return comp;
}

void solve_component(vector<int>& c, int n, vector<vector<int> >& p, vector<vector<int> >& adi, bool& pos){

    vector<int> cycle;
    vector<bool> vis(n);
    for(auto v: c){
        if(vis[v]) continue;

        cycle.push_back(v);
        for(auto u: c){

            if(u!=v && p[v][u]==1){
                adi[v][u]=1;
                adi[u][v]=1;

                vis[u]=true;

                for(int i=0; i<n; i++){
                    pos = pos && (p[v][i] == p[u][i]);
                }
            }
        }
    }

    for(int i=0; i+1<(int)cycle.size(); i++){
        adi[cycle[i]][cycle[i+1]]=1;
        adi[cycle[i+1]][cycle[i]]=1;
    }
    if(cycle.size()>1){
        adi[cycle[0]][cycle.back()]=1;
        adi[cycle.back()][cycle[0]]=1;
    }

    if(cycle.size()==2){
        pos=false;
    }
}

int construct(vector<vector<int> > p) {
	int n = p.size();
	
    bool pos=true;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==3){
                pos=false;
            }
        }
    }
	
	vector<vector<int> > comp=components(p, n, pos);


    vector<vector<int> > adi(n, vector<int> (n, 0));
    for(auto c: comp){
        solve_component(c, n, p, adi, pos);
    }

    if(pos){
        build(adi);
        return 1;
    }
    return 0;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<vector<int> > p(n, vector<int> (n));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> p[i][j];
        }
    }

    cout << construct(p) << "\n";
}*/

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