Submission #615791

#	Time	Username	Problem	Language	Result	Execution time	Memory
615791		Iwanttobreakfree	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	244 ms	24052 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
void line(vector<int>& v,vector<vector<int>>& ans,vector<int>& id){
    for(int i=1;i<v.size();i++){
        ans[v[i]][v[i-1]]=1;
        id[id[v[i]]]=id[v[0]];
    }
}
bool check(int a,int b,vector<vector<int>>& p,vector<bool>& seen){
    seen[a]=seen[b]=true;
    for(int i=0;i<p.size();i++){
        if(p[a][i]!=p[b][i])return false;
    }
    return true;
}
int build_1(vector<vector<int>>& ans,vector<int>& id,vector<vector<int>>& p){
    int n=ans.size();
    vector<bool> seen(n,false);
    vector<vector<int>> lines(n);
    for(int i=0;i<n;i++){
        if(seen[i])continue;
        lines[i].push_back(i);
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(p[i][j]==1){
                if(!check(i,j,p,seen))return 0;
                lines[i].push_back(j);
            }
        }
    }
    for(int i=0;i<n;i++)line(lines[i],ans,id);
    return 1;
}
int cycle(vector<int>& v,vector<vector<int>>& ans,vector<int>& id){
    if(v.size()==2)return 0;
    if(v.size()<=1)return 1;
    //for(int x:v)cout<<x<<' ';
    line(v,ans,id);
    ans[v[0]][v[v.size()-1]]=1;
    return 1;
}
int build_2(vector<vector<int>>& ans,vector<int>& id,vector<vector<int>>& p){
    if(!build_1(ans,id,p))return 0;
    int n=ans.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)if(p[i][j]==1)p[i][j]=2;
    }
    vector<bool> seen(n,false);
    vector<vector<int>> cycles(n);
    for(int i=0;i<n;i++){
        if(seen[i]||id[i]!=i)continue;
        cycles[i].push_back(i);
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(p[i][j]==2&&!seen[j]&&id[j]==j){
                if(!check(i,j,p,seen))return 0;
                cycles[i].push_back(j);
            }
        }
    }
    for(int i=0;i<n;i++)if(!cycle(cycles[i],ans,id))return 0;
    return 1;
}
int construct(vector<vector<int>> p){
	int n = p.size();
	vector<int> id(n);
	for(int i=0;i<n;i++){
        p[i][i]=0;
        id[i]=i;
	}
	vector<vector<int>> answer(n,vector<int>(n));
    int mx=0;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)mx=max(mx,p[i][j]);
    for(int i=0;i<n;i++)p[i][i]=1;
    if(mx==3)return 0;
    if(mx==1){
        if(!build_1(answer,id,p))return 0;
    }
    if(mx==2){
        if(!build_2(answer,id,p))return 0;
    }
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(answer[i][j])answer[j][i]=1;
    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cout<<answer[i][j]<<' ';
        cout<<'\n';
    }*/
	build(answer);
	return 1;
}
/*int main(){
    vector<vector<int>> v={{1,1,2,2},{1,1,2,2},{2,2,1,2},{2,2,2,1}};
    //vector<vector<int>> w={{1,1},{1,1}};
    construct (v);
}*/

Compilation message (stderr)

supertrees.cpp: In function 'void line(std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&)':
supertrees.cpp:6:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for(int i=1;i<v.size();i++){
      |                 ~^~~~~~~~~
supertrees.cpp: In function 'bool check(int, int, std::vector<std::vector<int> >&, std::vector<bool>&)':
supertrees.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<p.size();i++){
      |                 ~^~~~~~~~~

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