Submission #637310

#	Time	Username	Problem	Language	Result	Execution time	Memory
637310		fadi57	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	457 ms	26444 KiB

supertrees

#include "supertrees.h"
#include <vector>
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
int par[mx],par2[mx];std::vector<std::vector<int>> answer;	int ok=1;
int n;
void init(int n){
  for(int i=0;i<=n;i++){
    par[i]=i;
    par2[i]=i;
  }
 
}
int fin(int a){
  if(par[a]==a){
    return a;
  }else{
    return par[a]=fin(par[a]);
  }
 
}
int fin2(int a){
  if(par2[a]==a){
    return a;
  }else{
    return par2[a]=fin2(par2[a]);
  }
 
}
int uni(int a,int b){
 
  a=fin(a);  b=fin(b);
  if(a==b){return 1;}
  par[a]=b;
return 0;
 
 
 }
 int uni2(int a,int b){
 
  a=fin2(a);  b=fin2(b);
  if(a==b){return 1;}
  par2[a]=b;
   return 0;
  }
 int conect(int x){
 
    vector<int>v,nodes[mx];
 
  //  cout<<"TEST "<<x<<endl;
   for(int i=0;i<n;i++){
      if(fin(i)==x){
            int y=fin2(i);
         //  cout<<i<<"  "<<y<<endl;;
        v.push_back(i);
      }
 
   }
 
   set<int>tree;
   for(int i=0;i<v.size();i++){
     // tree.insert(fin2(v[i]));
      int x=fin2(v[i]);
      nodes[x].push_back(v[i]);
 
 
   }
   vector<int>heads;
   for(int i=0;i<n;i++){
      if(nodes[i].size()!=0){
        heads.push_back(i);
        for(int j=0;j<nodes[i].size()-1;j++){
                int me= nodes[i][j];int nxt=nodes[i][j+1];
            answer[me][nxt]=answer[nxt][me]=1;
 
        }
      }
 
   }
 //  cout<<" hello "<<heads.size()<<endl;
   if(heads.size()==2){ok=0;return 0;}
   if(heads.size()==1){return 0;}
   for(int i=0;i<heads.size();i++){
     //   cout<<" helo "<<heads[i]<<endl;
    int me=heads[i];int nxt=heads[(i+1)%heads.size()];
    answer[me][nxt]=1; answer[nxt][me]=1;
   }
   return 0;
 
  }
int construct(vector<vector<int>> p) {
	 n = p.size();
   init(n);
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
           if(p[i][j]) uni(i,j);
           if(p[i][j]==1){uni2(i,j);}
        }
	}
 
		for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
          if(p[i][j]==0&&fin(i)==fin(j))ok=0;
        }
	}
	if(ok==0){return 0;}
	vector<int>comp[n+5];
     for(int i=0;i<n;i++){
        conect(i);
        if(ok==0){return 0;}
 
    }
    for(int i=0;i<n;i++){
         for(int j=0;j<n;j++){
         //   cout<<answer[i][j]<<" ";
         }
       //  cout<<endl;
    }
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int conect(int)':
supertrees.cpp:55:17: warning: unused variable 'y' [-Wunused-variable]
   55 |             int y=fin2(i);
      |                 ^
supertrees.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for(int i=0;i<v.size();i++){
      |                ~^~~~~~~~~
supertrees.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int j=0;j<nodes[i].size()-1;j++){
      |                     ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int i=0;i<heads.size();i++){
      |                ~^~~~~~~~~~~~~

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