Submission #740019

#	Time	Username	Problem	Language	Result	Execution time	Memory
740019		abczz	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	216 ms	26296 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], R[1000][1000];
ll n, a, b, z, 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;
    if (B[u]) X[u].push_back(v);
    else if (B[v]) X[v].push_back(u);
    a = dsu(u), b = dsu(v);
    if (a == b) return 0;
  }
  for (int i=0; i<n; ++i) {
    if (B[i] && X[i].size() == 1) return 0;
  }
	for (int i=0; i<n; ++i) {
    if (B[i] && X[i].size()) {
      a = dsu(i);
      if (R[a][X[i][0]]) continue;
      R[a][X[i][0]] = true;
      if (D[X[i][0]]) {
        F[i][X[i][0]] = F[X[i][0]][i] = 1;
        for (int j=0; j<X[i].size(); ++j) {
          if (!D[X[i][j]]) return 0;
        }
        continue;
      }
      F[i][X[i][0]] = F[X[i][0]][i] = 1;
      for (int j=0; j+1<X[i].size(); ++j) {
        D[X[i][j]] = true;
        F[X[i][j]][X[i][j+1]] = F[X[i][j+1]][X[i][j]] = 1;
      }
      D[X[i].back()] = true;
      F[i][X[i].back()] = F[X[i].back()][i] = 1;
    }
  }
  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:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j=0; j<X[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~
supertrees.cpp:75:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |       for (int j=0; j+1<X[i].size(); ++j) {
      |                     ~~~^~~~~~~~~~~~
supertrees.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i=1; i<Z.size(); ++i) {
      |                   ~^~~~~~~~~
supertrees.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i=0; i+1<Y.size(); ++i) {
      |                   ~~~^~~~~~~~~

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