Submission #329113

#	Time	Username	Problem	Language	Result	Execution time	Memory
329113		chenwz	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	261 ms	24316 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef vector<int> IVec;

void addEdge(int u, int v, vector<IVec>& G) { G[u][v] = G[v][u] = 1; }

int construct(vector<IVec> p) {
  int n = p.size();
  for (int i = 0; i < n; i++) // if p(i,j) == 3, there must be another p(i`,j`) ≥4 ??
    if (find(p[i].begin(), p[i].end(), 3) != p[i].end()) return 0;
  vector<vector<int>> G(n, IVec(n));
  vector<bool> Vis(n);
  IVec CC(n), TreeID(n);
  for (int u = 0; u < n; u++) {
    if (Vis[u]) continue;
    queue<int> cycleQ; cycleQ.push(u);
    IVec cycle; // cycle containing u
    while (!cycleQ.empty()) {
      int root = cycleQ.front(); cycleQ.pop();
      if (Vis[root]) continue;
      IVec tree; // tree contains root
      queue<int> treeQ; treeQ.push(root);
      cycle.push_back(root);
      while (!treeQ.empty()) { // bfs to mark all points in tree root
        int v = treeQ.front(); treeQ.pop();
        if (Vis[v]) continue;
        tree.push_back(v), TreeID[v] = root;
        Vis[v] = true, CC[v] = u;
        for (int i = 0; i < n; i++) {
          if (p[v][i] == 2) cycleQ.push(i); // v and i should on same circle
          else if (p[v][i] == 1) treeQ.push(i); // v and i on same tree
        }
      }
      for (size_t i = 0; i + 1 < tree.size(); i++)
        addEdge(tree[i], tree[i + 1], G);
    }
    int csz = cycle.size();
    if (csz == 2) return 0;
    if (csz > 2)
      for (int i = 0; i < csz; i++) addEdge(cycle[i], cycle[(i + 1) % csz], G);
  }

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int pc = p[i][j];
      if (TreeID[i] == TreeID[j]) { if (pc != 1) return 0; }
      else if (CC[i] == CC[j]) { if (pc != 2) return 0; }
      else { if (pc) return 0; }
    }
  }
  build(G);
  return 1;
}

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