Submission #583465

#	Time	Username	Problem	Language	Result	Execution time	Memory
583465		TimDee	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	216 ms	24016 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
#define all(a) a.begin(), a.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define pi pair<int,int>
#define f first
#define s second

int mirror(vector<vector<int>>&a) {
  int n=a.size();
  for (int i=0; i<n; ++i) {
    for (int j=i+1; j<n; ++j) {
      if (a[i][j]!=a[j][i]) return 0;
    }
  }
  return 1;
}

int construct(std::vector<std::vector<int>> p) {
  int n = p.size();
  
  vector<vector<int>> a(n); 
  forn(i,n) a[i].assign(n,0);

  if (!mirror(p)) return 0;

  queue<int> q;
  q.push(0);

  vector<pair<int,int>> edges;
  vector<int> vis(n,0);

  while (!q.empty()) {

  int v=q.front(); q.pop();
  if (vis[v]) continue;

  vis[v]=1;

  vector<int> one, two;
  for (int i=0; i<n; ++i) {
    if (vis[i]) continue;
    if (p[v][i]==1) one.pb(i);
    else if (p[v][i]==2) two.pb(i);
    else q.push(i);
  }

  for (int i=0; i<one.size(); ++i) {
    for (int j=i+1; j<one.size(); ++j) {
      if (p[i][j]!=1) return 0;
    }
  }
  for (auto u:one) edges.pb(mp(u,v));

  pi P = {-1,-1};

  if (!two.size()) continue;
  if (two.size()==1) return 0;
  for (int i=0; i<two.size(); ++i) {
    for (int j=i+1; j<two.size(); ++j) {
      if (p[two[i]][two[j]]==2) P={two[i],two[j]};
    }
  }

  if (P.f==-1 && P.s==-1) return 0;

  int X=P.f, Y=P.s;
  vis[X]=vis[Y]=1;
  //edges.pb(mp(v,X)); edges.pb(mp(v,Y)); //edges.pb(mp(X,Y));

  vector<int> cycle = {v,X,Y};

  for (auto u:two) {
    vis[u]=1;
    if (u==X || u==Y) continue;
    if (p[X][u]==1 && p[Y][u]==1) return 0;
    if (p[X][u]==1) edges.pb(mp(X,u));
    else if (p[Y][u]==1) edges.pb(mp(Y,u));
    else cycle.pb(u);
  }

  for (int i=0; i<cycle.size(); ++i) edges.pb(mp(cycle[i],cycle[(i+1)%cycle.size()]));

  }

  for (auto E:edges) {
    int u=E.f, v=E.s;
    a[u][v]=1;
    a[v][u]=1;
  }

  build(a);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int i=0; i<one.size(); ++i) {
      |                 ~^~~~~~~~~~~
supertrees.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int j=i+1; j<one.size(); ++j) {
      |                     ~^~~~~~~~~~~
supertrees.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i=0; i<two.size(); ++i) {
      |                 ~^~~~~~~~~~~
supertrees.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int j=i+1; j<two.size(); ++j) {
      |                     ~^~~~~~~~~~~
supertrees.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int i=0; i<cycle.size(); ++i) edges.pb(mp(cycle[i],cycle[(i+1)%cycle.size()]));
      |                 ~^~~~~~~~~~~~~

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