Submission #496168

#	Time	Username	Problem	Language	Result	Execution time	Memory
496168		Alex_tz307	슈퍼트리 잇기 (IOI20_supertrees)	C++17	100 / 100	211 ms	28100 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

struct DSU {
  vector<int> p, sz;

  DSU(int n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    sz.assign(n, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool connected(int u, int v) {
    return root(u) == root(v);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[y] < sz[x]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
};

const int kN = 1e3;
vector<vector<int>> g;
bitset<kN> vis;
vector<int> comp;

void dfs(int u) {
  vis[u] = true;
  comp.emplace_back(u);
  for (int v : g[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	DSU dsu(n);
	vector<vector<int>> sol(n, vector<int>(n));
	g.resize(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (p[i][j] == 3) {
        return 0;
      }
      if (p[i][j] == 1 && dsu.unite(i, j)) {
        sol[i][j] = sol[j][i] = 1;
      }
      if (p[i][j] == 2) {
        g[i].emplace_back(j);
      }
    }
  }
  DSU cycles(n);
  for (int i = 0; i < n; ++i) {
    if (!vis[dsu.root(i)]) {
      comp.clear();
      dfs(i);
      for (int &v : comp) {
        v = dsu.root(v);
        vis[v] = true;
      }
      sort(comp.begin(), comp.end());
      comp.erase(unique(comp.begin(), comp.end()), comp.end());
      int m = comp.size();
      if (m == 2) {
        return 0;
      }
      if (m == 1) {
        continue;
      }
      for (int j = 0; j < m; ++j) {
        int k = comp[(j + 1) % m];
        sol[comp[j]][k] = sol[k][comp[j]] = 1;
        cycles.unite(comp[j], k);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (p[i][j] == 0 && (dsu.connected(i, j) || cycles.connected(i, j))) {
        return 0;
      }
    }
  }
  build(sol);
	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