Submission #593599

#	Time	Username	Problem	Language	Result	Execution time	Memory
593599		kenjinemera	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	234 ms	24096 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

/* 
    Sub 1 + 2: Construct numerous connected components
    Sub 3: Add cycle to the numerous components (break if component size == 2)
    Sub 4: Build many trees and loop around their roots
    Sub 5: Verify that Law Of Tree works
    Sub 6: We can't allow 3 since we would need 4
*/

typedef long long int64;
#define pb push_back
#define f first
#define s second
#define vi vector<int>

const int MAXN = 1010;
bool vis[MAXN];

int construct(vector<vector<int>> p)
{
	int n = p.size();
	vector<vi> answer;

	for (int i = 0; i < n; i++) {
		vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

    for (int i = 0; i < n - 1; i++)
    {
          if (vis[i]) continue;
          int cycle_count = 1;
          int prev_link = i;
    
          // how are we going to verify the law of the tree?
    
          for (int j =  i + 1; j < n; j++)
          {
              if (p[i][j] == 3) return 0;
              if (p[i][j] == 0) continue;
    
              vis[j] = 1;
    
              if (p[i][j] == 2)
              {
                  answer[prev_link][j] = 1;
                  answer[j][prev_link] = 1;
                  prev_link = j;
                  cycle_count++;

                  for (int k = j + 1; k < n; k++)
                  {
                        if (p[j][k] == 1) {
                            answer[j][k] = 1;
                            answer[k][j] = 1;
                            vis[k] = 1;
                        }
                  }

              } else if (p[i][j] == 1)
              {
                  answer[i][j] = 1;
                  answer[j][i] = 1;
                  vis[j] = 1;
              }                          
          }
    
          if (cycle_count == 2) return 0;
          else if (cycle_count > 2) {
              answer[i][prev_link] = 1;
              answer[prev_link][i] = 1;
          }
    }

    build(answer);
	return 1;
}

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