Submission #309938

#	Time	Username	Problem	Language	Result	Execution time	Memory
309938		Genius1506	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	275 ms	22396 KiB

supertrees

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

const int mxN = 1002;
int par[mxN];
void init(int n){
    for(int i = 0; i <= n; i++)
        par[i] = i;
}
int find(int x){
    if(par[x]!=x)
        return par[x] = find(par[x]);
    return par[x];
}
void merge(int x, int y){
    x = find(x);
    y = find(y);
    if(x==y)
        return;
    par[x]=y;
}
int construct(vector<vector<int>> p){
    for(auto x : p){
        for(auto y: x)
            if(y==3)
                return 0;
    }
    int n = p.size();
    vector<vector<int>>ans(n,vector<int>(n,0)),comp(n,vector<int>()),tree(n,vector<int>());
    init(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j])
                merge(i,j);
        }
    }
    for(int i = 0; i < n; i++)
        comp[find(i)].push_back(i);
    init(n);
    for(int i = 0; i < n; i++){
        for(int c1 : comp[i]){
            for(int c2 : comp[i]){
                if(p[c1][c2]==0)
                    return 0;
                else if(p[c1][c2]==1)
                    merge(c1,c2);
            }
        }
        vector<int>cycle;
        for(int x : comp[i]){
            if(find(x)==x)
                cycle.push_back(x);
            tree[find(x)].push_back(x);
        }
        if(cycle.size()==2)
            return 0;
        if(cycle.size()==1)
            continue;
        for(int j=0;j<cycle.size();j++){
            int x = (j+1==cycle.size()?0:j+1);
            ans[cycle[j]][cycle[x]]=1;
            ans[cycle[x]][cycle[j]]=1;
        }
    }
    for(int i = 0; i < n; i++){
        if(tree[i].size()==0)
            continue;
        int repn = tree[i][0];
        for(int j = 1; j < tree[i].size(); j++){
            ans[repn][tree[i][j]]=1;
            ans[tree[i][j]][repn]=1;
        }
    }
    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j=0;j<cycle.size();j++){
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             int x = (j+1==cycle.size()?0:j+1);
      |                      ~~~^~~~~~~~~~~~~~
supertrees.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j = 1; j < tree[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~

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