Submission #779143

#	Time	Username	Problem	Language	Result	Execution time	Memory
779143		jasmin	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	340 KiB

supertrees

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

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

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

        comp.push_back({});
        for(int u=0; u<v; u++){
            if(p[v][u]!=0){

                comp.back().push_back(u);
                if(vis[u]) pos=false;
                vis[u]=true;
            }
        }
    }
    
    return comp;
}

void solve_component(vector<int>& c, int n, vector<vector<int> >& p, vector<vector<int> >& adi, bool& pos){
    int m=c.size();

    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;
    }
    adi[cycle[0]][cycle.back()]=1;
    adi[cycle.back()][cycle[0]]=1;
}

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(int i=0; i<n; i++){
        adi[i][i]=1;
    }
    for(auto c: comp){
        solve_component(c, n, p, adi, pos);
    }

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

Compilation message (stderr)

supertrees.cpp: In function 'void solve_component(std::vector<int>&, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, bool&)':
supertrees.cpp:28:9: warning: unused variable 'm' [-Wunused-variable]
   28 |     int m=c.size();
      |         ^

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