Submission #303122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
303122	2020-09-19T22:36:03 Z	VROOM_VARUN	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	261 ms	26104 KB

supertrees

/*
ID: varunra2
LANG: C++
TASK: supertrees
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n;
VVI p;
VVI ret;

bool isBad() {
  for (int i = 0; i < n; i++) {
    if (p[i][i] != 1) return false;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (p[i][j] != p[j][i]) return false;
    }
  }

  return true;
  // change/update later
}

void dfs(int i, vector<bool>& vis, int bnd, VI& cmp) {
  if (vis[i]) return;
  vis[i] = true;
  cmp.PB(i);
  for (int ii = 0; ii < n; ii++) {
    if (i == ii) continue;
    if (p[i][ii] >= bnd) {
      dfs(ii, vis, bnd, cmp);
    }
  }
}

// void solve(VI& comp) {

// }

struct dsu {
  VI par;
  VI siz;
  int n;
  void init(int _n) {
    n = _n;
    par.resize(n);
    siz.resize(n);
    for (int i = 0; i < n; i++) {
      par[i] = i;
      siz[i] = 1;
    }
  }

  bool ispar(int x) { return x == par[x]; }

  int find(int x) {
    while (par[x] != par[par[x]]) par[x] = par[par[x]];
    return par[x];
  }

  bool same(int x, int y) { return find(x) == find(y); }

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    // if (siz[x] < siz[y]) swap(x, y);
    par[y] = x;
    siz[x] += siz[y];
  }
};

void edge(int u, int v) {
  // make an edge between u and v
  if (u < 0 or v < 0 or u >= n or v >= n) return;

  ret[u][v] = 1;
  ret[v][u] = 1;
}

int buildcycle(VI& comp) {
  // build a cycle, first element is the parent
  if (sz(comp) == 1) return 1;
  if(sz(comp) == 2) return 0;
  edge(comp[0], comp.back());
  for (int i = 0; i < sz(comp) - 1; i++) {
    edge(comp[i], comp[i + 1]);
  }
  return 1;
}

void buildtree(VI& comp) {
  // build tree, first element is root
  for (int i = 1; i < sz(comp); i++) {
    edge(comp[0], comp[i]);
  }
}

// void build(VVI& a) {
//   // bruh
//   // debug(a);
//   debug("here");
//   for (int i = 0; i < n; i++) {
//     debug(i, a[i]);
//   }
// }

int construct(VVI asdf) {
  n = sz(asdf);
  p = asdf;

  ret.resize(n);

  trav(x, asdf) trav(y, x) if (y == 3) return 0;

  for (int i = 0; i < n; i++) {
    ret[i].resize(n);
  }

  // vector<bool> vis(n, false);

  // for(int i = 0; i < n; i++) {
  // if(vis[i]) continue;
  // VI comp;
  // dfs(i, vis, 1, comp);
  // solve(comp);
  // }

  // merge all 2's together
  //

  dsu g1, g2;

  g1.init(n);
  g2.init(n);

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (p[i][j] >= 1)
        if (!g1.same(i, j)) g1.merge(i, j);
      if (p[i][j] >= 2)
        if (!g2.same(i, j)) g2.merge(i, j);
    }
  }

  // if we need to connect 2 nodes, we do it through their parent in dsu2

  for (int i = 0; i < n; i++) {
    if (g2.ispar(i)) {
      VI comp;
      comp.PB(i);
      for (int j = 0; j < n; j++) {
        if (g2.find(j) == i and j != i) {
          comp.PB(j);
        }
      }
      int res = buildcycle(comp);
      if(!res) return 0;
    }
  }

  for (int i = 0; i < n; i++) {
    if (g1.ispar(i)) {
      VI comp;
      comp.PB(i);
      for (int j = 0; j < n; j++) {
        if (g2.ispar(j) and g1.find(j) == i and j != i) {
          comp.PB(j);
        }
      }
      buildtree(comp);
    }
  }

  build(ret);
  return 1;
}

// int main() {
// #ifndef ONLINE_JUDGE
//   freopen("supertrees.in", "r", stdin);
//   freopen("supertrees.out", "w", stdout);
// #endif
//   cin.sync_with_stdio(0);
//   cin.tie(0);

//   int n;
//   cin >> n;

//   VVI vals(n, VI(n));

//   for (int i = 0; i < n; i++) {
//     for (int j = 0; j < n; j++) {
//       cin >> vals[i][j];
//     }
//   }

//   int x = construct(vals);

//   debug(x);

//   return 0;
// }

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	246 ms	26104 KB	Output is correct

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	246 ms	26104 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	10 ms	1408 KB	Output is correct
13	Correct	246 ms	26104 KB	Output is correct
14	Incorrect	0 ms	256 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	10 ms	1408 KB	Output is correct
9	Correct	246 ms	26064 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	13 ms	1420 KB	Output is correct
13	Correct	245 ms	26104 KB	Output is correct
14	Incorrect	0 ms	288 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	65 ms	6776 KB	Output is correct
5	Correct	243 ms	26104 KB	Output is correct
6	Correct	242 ms	26104 KB	Output is correct
7	Correct	261 ms	26104 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	61 ms	6776 KB	Output is correct
10	Correct	238 ms	26104 KB	Output is correct
11	Correct	241 ms	26104 KB	Output is correct
12	Correct	247 ms	26104 KB	Output is correct
13	Correct	0 ms	256 KB	Output is correct
14	Correct	0 ms	256 KB	Output is correct
15	Incorrect	0 ms	256 KB	Too many ways to get from 0 to 4, should be 1 found no less than 2
16	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	246 ms	26104 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	10 ms	1408 KB	Output is correct
13	Correct	246 ms	26104 KB	Output is correct
14	Incorrect	0 ms	256 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	11 ms	1408 KB	Output is correct
7	Correct	246 ms	26104 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	0 ms	256 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	10 ms	1408 KB	Output is correct
13	Correct	246 ms	26104 KB	Output is correct
14	Incorrect	0 ms	256 KB	Answer gives possible 1 while actual possible 0
15	Halted	0 ms	0 KB	-