Submission #740057

#	Time	Username	Problem	Language	Result	Execution time	Memory
740057		abczz	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	235 ms	27788 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, 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;
    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() == 1) return 0;
  }
	for (int i=0; i<n; ++i) {
    if (B[i] && X[i].size()) {
      /*cout << i << " " << X[i].size() << endl;
      for (auto u : X[i]) {
        cout << u << " ";
      }
      cout << endl;*/
      D[i] = true;
      a = dsu(i), b = dsu(X[i][0]);
      if (a != b) {
        P[a] = b;
        F[i][X[i][0]] = F[X[i][0]][i] = 1;
      }
      for (int j=0; j+1<X[i].size(); ++j) {
        a = dsu(X[i][j]), b = dsu(X[i][j+1]);
        D[X[i][j]] = true;
        if (a != b) {
          z = X[i][j+1];
          P[a] = b;
          F[X[i][j]][X[i][j+1]] = F[X[i][j+1]][X[i][j]] = 1;
        }
      }
      D[X[i].back()] = true;
      F[i][z] = F[z][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: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:98:20: 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=1; i<Z.size(); ++i) {
      |                   ~^~~~~~~~~
supertrees.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i=0; i+1<Y.size(); ++i) {
      |                   ~~~^~~~~~~~~

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