Submission #740069

#	Time	Username	Problem	Language	Result	Execution time	Memory
740069		abczz	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	197 ms	28476 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <vector>
#include <array>
#define ll int

using namespace std;

vector <ll> X[1000];
vector <ll> Z, Y, W;
vector<array<ll, 2>> V[3];
vector<vector<int>> F;
vector <int> tmp;
bool B[1000], D[1000], E[1000];
ll n, a, b, y, z, cnt, P[1000], G[1000];
ll dsu(ll u) {
	if (P[u] == u) return u;
	else return P[u] = dsu(P[u]);
}
int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	for (int i=0; i<n; ++i) P[i] = i;
	for (int i=0; i<n; ++i) {
		F.push_back(tmp);
		for (int j=0; j<n; ++j) {
			F[i].push_back(0);
			if (p[i][j] == 3) return 0;
			if (p[i][j]) {
				a = dsu(i), b = dsu(j);
				if (a != b) P[a] = b;
			}
      if (j > i) V[p[i][j]].push_back({i, j});
		}
	}
	for (auto [u, v] : V[0]) {
		a = dsu(u), b = dsu(v);
		if (a == b) return 0;
	}
  for (int i=0; i<n; ++i) {
    a = dsu(i);
    G[i] = a;
  }
	for (int i=0; i<n; ++i) P[i] = i;
	for (auto [u, v] : V[1]) {
		a = dsu(u), b = dsu(v);
		if (a != b) {
			P[a] = b;
			B[u] = B[v] = true;
			F[u][v] = F[v][u] = 1;
		}
	}
  for (auto [u, v] : V[2]) {
    E[u] = E[v] = 1;
    a = dsu(u), b = dsu(v);
    if (B[u]) X[u].push_back(v);
    if (B[v]) X[v].push_back(u);
    if (a == b) return 0;
  }
	for (int i=0; i<n; ++i) {
    if (B[i] && X[i].size()) {
      cnt = 0;
      D[i] = true;
      a = dsu(i), b = dsu(X[i][0]);
      y = i;
      if (a != b) {
        P[a] = b;
        ++cnt;
        y = X[i][0];
        F[i][X[i][0]] = F[X[i][0]][i] = 1;
      }
      z = -1;
      for (int j=0; j+1<X[i].size(); ++j) {
        a = dsu(y), b = dsu(X[i][j+1]);
        D[X[i][j]] = true;
        if (a != b) {
          F[y][X[i][j+1]] = F[X[i][j+1]][y] = 1;
          ++cnt;
          y = z = X[i][j+1];
          P[a] = b;
        }
      }
      D[X[i].back()] = true;
      if (z != -1) {
        ++cnt;
        F[i][z] = F[z][i] = 1;
      }
      if (cnt == 1) return 0;
    }
  }
  for (int i=0; i<n; ++i) {
    if (!B[i] && !D[i] && E[i]) {
      Z.push_back(i);
    }
  }
  while (Z.size()) {
    Y.clear();
    W.clear();
    if (Z.size() <= 2) return 0;
    Y.push_back(Z[0]);
    for (int i=1; i<Z.size(); ++i) {
      if (G[Z[0]] == G[Z[i]]) Y.push_back(Z[i]);
      else W.push_back(Z[i]);
    }
    if (Y.size() <= 2) return 0;
    for (int i=0; i+1<Y.size(); ++i) {
      F[Y[i]][Y[i+1]] = F[Y[i+1]][Y[i]] = 1;
    }
    F[Y[0]][Y.back()] = F[Y.back()][Y[0]] = 1;
    swap(Z, W);
  }
	build(F);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |  for (auto [u, v] : V[0]) {
      |            ^
supertrees.cpp:44:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |  for (auto [u, v] : V[1]) {
      |            ^
supertrees.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |   for (auto [u, v] : V[2]) {
      |             ^
supertrees.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |       for (int j=0; j+1<X[i].size(); ++j) {
      |                     ~~~^~~~~~~~~~~~
supertrees.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i=1; i<Z.size(); ++i) {
      |                   ~^~~~~~~~~
supertrees.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i=0; i+1<Y.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