Submission #412385

#	Time	Username	Problem	Language	Result	Execution time	Memory
412385		kimbj0709	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	374 ms	28516 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
void build(vector<vector<int> > ans);
#define maxn 1050
vector<set<int> > adj(maxn);
int cnt[maxn][maxn];
unordered_set<int> set1;
void merge(vector<int> &vect1,vector<int> &vect2){
  for(auto k:vect2){
    vect1.push_back(k);
  }
  vect2.clear();
}
void dfs(int node,int parent,int startnode){
  set1.insert(node);
  //cout << node << " " << parent << " " << startnode << endl;
  cnt[startnode][node]++;
  for(auto k:adj[node]){
    if(set1.find(k)!=set1.end()){
      continue;
    }
    dfs(k,node,startnode);
  }
  set1.erase(node);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
  std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(n,0);
		answer.push_back(row);
	}
  vector<vector<int> > vect1(n);
  vector<vector<int> > vect2(n);
  for(int i=0;i<n;i++){
    vect1[i].push_back(i);
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(p[i][j]==1&&vect1[i].size()!=0&&vect1[j].size()!=0){
        merge(vect1[i],vect1[j]);
        answer[i][j] = 1;
        answer[j][i] = 1;
        adj[i].insert(j);
        adj[j].insert(i);
      }
    }
  }
  for(int i=0;i<n;i++){
    if(vect1[i].size()!=0){
      vect2[i].push_back(i);
    }
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(p[i][j]==2&&vect2[i].size()!=0&&vect2[j].size()!=0){
        merge(vect2[i],vect2[j]);
      }
    }
  }
  for(int i=0;i<n;i++){
    if(vect2[i].size()>=2){
      for(int j=1;j<vect2[i].size();j++){
        answer[vect2[i][j-1]][vect2[i][j]] = 1;
        answer[vect2[i][j]][vect2[i][j-1]] = 1;
        adj[vect2[i][j-1]].insert(vect2[i][j]);
        adj[vect2[i][j]].insert(vect2[i][j-1]);
      }
      answer[vect2[i][0]][vect2[i][vect2[i].size()-1]] = 1;
      answer[vect2[i][vect2[i].size()-1]][vect2[i][0]] = 1;
      adj[vect2[i][0]].insert(vect2[i][vect2[i].size()-1]);
      adj[vect2[i][vect2[i].size()-1]].insert(vect2[i][0]);
    }
  }

  /*for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout << answer[i][j] << " ";
    }
    cout << endl;
  }*/
  for(int i=0;i<n;i++){
    dfs(i,-1,i);
  }
  /*for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout << cnt[i][j] << " ";
    }
    cout << endl;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout << answer[i][j] << " ";
    }
    cout << endl;
  }*/
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(cnt[i][j]!=p[i][j]){
        return 0;
      }
    }
  }
	build(answer);
	return 1;
}

/*

static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message) {
    if (!cond) {
        printf("%s\n", message.c_str());
        fclose(stdout);
        exit(0);
    }
}
void build(std::vector<std::vector<int>> _b) {
    check(!called, "build is called more than once");
    called = true;
    check((int)_b.size() == n, "Invalid number of rows in b");
    for (int i = 0; i < n; i++) {
        check((int)_b[i].size() == n, "Invalid number of columns in b");
    }
    b = _b;
}

int main() {
    assert(scanf("%d", &n) == 1);
    
    p.resize(n);
    for (int i = 0; i < n; i++) {
        p[i].resize(n);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            assert(scanf("%d", &p[i][j]) == 1);
        }
    }
    fclose(stdin);

    int possible = construct(p);

    check(possible == 0 || possible == 1, "Invalid return value of construct");
    if (possible == 1) {
        check(called, "construct returned 1 without calling build");
    } else {
        check(!called, "construct called build but returned 0");
    }

    printf("%d\n", possible);
    if (possible == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) {
                    printf(" ");
                }
                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }
    fclose(stdout);
}
*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |       for(int j=1;j<vect2[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