Submission #636386

#	Time	Username	Problem	Language	Result	Execution time	Memory
636386		ghostwriter	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	248 ms	30492 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int MAXN = 1005;
int N, P[MAXN][MAXN], adj[MAXN][MAXN], p1[MAXN], s[MAXN], c[MAXN], cnt = 0;
bitset<MAXN> d[MAXN];
vi nodes, cc[MAXN];
int getp(int i) { return i == p1[i]? i : p1[i] = getp(p1[i]); }
bool join(int x, int y) {
	x = getp(x);
	y = getp(y);
	if (x == y) return 0;
	if (s[y] > s[x]) swap(x, y);
	p1[y] = x;
	s[x] += s[y];
	return 1;
}
void dfs(int u) {
	c[u] = 1;
	nodes.pb(u);
	FOR(v, 0, N - 1) {
		if (!P[u][v] || c[v]) continue;
		dfs(v);
	}
}
void dfs1(int u) {
	c[u] = 1;
	cc[cnt].pb(u);
	FOR(v, 0, N - 1) {
		if (P[u][v] != 1 || c[v]) continue;
		dfs1(v);
	}
}
void dfs2(int u) {
	c[u] = 1;
	nodes.pb(u);
	FOR(v, 1, cnt) {
		if (!adj[u][v] || c[v]) continue;
		dfs2(v);
	}
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	N = n;
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(n, 0);
		ans.push_back(row);
	}
	FOR(i, 0, n - 1)
	FOR(j, 0, n - 1)
		P[i][j] = p[i][j];
	int sub6 = 0;
	FOR(i, 0, n - 1)
	FOR(j, 0, n - 1)
		if (p[i][j] == 3)
			sub6 = 1;
	if (sub6) return 0;
	bool sub1 = 1;
	EACH(i, p)
	EACH(j, i)
		if (j != 1)
			sub1 = 0;
	if (sub1) {
		FOR(i, 0, n - 2) ans[i][i + 1] = ans[i + 1][i] = 1;
		build(ans);
		return 1;
	}
	bool connectivity = 1;
	FOR(i, 0, n - 1)
	FOR(j, 0, n - 1)
		d[i][j] = (p[i][j]? 1 : 0);
	FOR(i, 0, n - 1)
	FOR(j, 0, n - 1)
		if (!d[i][j]) {
			bitset<MAXN> cur = d[i] & d[j];
			int cnt = cur.count();
			if (cnt) connectivity = 0;
		}
	if (!connectivity) return 0;
	bool sub2 = 1;
	EACH(i, p)
	EACH(j, i)
		if (j != 0 && j != 1)
			sub2 = 0;
	if (sub2) {
		FOR(i, 0, n - 1) {
			p1[i] = i;
			s[i] = 1;
		}
		FOR(i, 0, n - 1)
		FOR(j, 0, n - 1) {
			if (!p[i][j] || !join(i, j)) continue;
			ans[i][j] = ans[j][i] = 1;
		}
		build(ans);
		return 1;
	}
	bool sub3 = 1;
	FOR(i, 0, n - 1)	
	FOR(j, 0, n - 1)
		if (i != j && p[i][j] != 0 && p[i][j] != 2)
			sub3 = 0;
	if (sub3) {
		FOR(i, 0, n - 1) {
			if (c[i]) continue;
			nodes.clear();
			dfs(i);
			if (sz(nodes) == 1) continue;
			if (sz(nodes) == 2) return 0;
			FOR(j, 0, sz(nodes) - 2) ans[nodes[j]][nodes[j + 1]] = ans[nodes[j + 1]][nodes[j]] = 1;
			ans[nodes[0]][nodes.back()] = ans[nodes.back()][nodes[0]] = 1;
		}
		build(ans);
		return 1;
	}
	FOR(i, 0, n - 1) {
		if (c[i]) continue;
		++cnt;
		dfs1(i);
		FOR(j, 0, sz(cc[cnt]) - 2) ans[cc[cnt][j]][cc[cnt][j + 1]] = ans[cc[cnt][j + 1]][cc[cnt][j]] = 1;
	}
	FOR(i, 1, cnt)
	FOR(j, 1, cnt) {
		if (i == j) continue;
		bool ok = 0;
		EACH(x, cc[i])
		EACH(y, cc[j])
			if (p[x][y] == 2)
				ok = 1;
		if (!ok) continue;
		EACH(x, cc[i])
		EACH(y, cc[j])
			if (p[x][y] != 2)
				ok = 0;
		if (!ok) return 0;
		adj[i][j] = 1;
	}
	memset(c, 0, sizeof c);
	FOR(i, 1, cnt) {
		if (c[i]) continue;
		nodes.clear();
		dfs2(i);
		if (sz(nodes) == 1) continue;
		if (sz(nodes) == 2) return 0;
		FOR(j, 0, sz(nodes) - 2) {
			int u = nodes[j], v = nodes[j + 1];
			ans[cc[u][0]][cc[v][0]] = ans[cc[v][0]][cc[u][0]] = 1;
		}
		int u = nodes.front(), v = nodes.back();
		ans[cc[u][0]][cc[v][0]] = ans[cc[v][0]][cc[u][0]] = 1;
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:56:2: note: in expansion of macro 'FOR'
   56 |  FOR(v, 0, N - 1) {
      |  ^~~
supertrees.cpp: In function 'void dfs1(int)':
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:64:2: note: in expansion of macro 'FOR'
   64 |  FOR(v, 0, N - 1) {
      |  ^~~
supertrees.cpp: In function 'void dfs2(int)':
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:72:2: note: in expansion of macro 'FOR'
   72 |  FOR(v, 1, cnt) {
      |  ^~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:85:2: note: in expansion of macro 'FOR'
   85 |  FOR(i, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:86:2: note: in expansion of macro 'FOR'
   86 |  FOR(j, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:89:2: note: in expansion of macro 'FOR'
   89 |  FOR(i, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:90:2: note: in expansion of macro 'FOR'
   90 |  FOR(j, 0, n - 1)
      |  ^~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:95:2: note: in expansion of macro 'EACH'
   95 |  EACH(i, p)
      |  ^~~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:96:2: note: in expansion of macro 'EACH'
   96 |  EACH(j, i)
      |  ^~~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:100:3: note: in expansion of macro 'FOR'
  100 |   FOR(i, 0, n - 2) ans[i][i + 1] = ans[i + 1][i] = 1;
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:105:2: note: in expansion of macro 'FOR'
  105 |  FOR(i, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:106:2: note: in expansion of macro 'FOR'
  106 |  FOR(j, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:108:2: note: in expansion of macro 'FOR'
  108 |  FOR(i, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:109:2: note: in expansion of macro 'FOR'
  109 |  FOR(j, 0, n - 1)
      |  ^~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:117:2: note: in expansion of macro 'EACH'
  117 |  EACH(i, p)
      |  ^~~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:118:2: note: in expansion of macro 'EACH'
  118 |  EACH(j, i)
      |  ^~~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:122:3: note: in expansion of macro 'FOR'
  122 |   FOR(i, 0, n - 1) {
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:126:3: note: in expansion of macro 'FOR'
  126 |   FOR(i, 0, n - 1)
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:127:3: note: in expansion of macro 'FOR'
  127 |   FOR(j, 0, n - 1) {
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:135:2: note: in expansion of macro 'FOR'
  135 |  FOR(i, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:136:2: note: in expansion of macro 'FOR'
  136 |  FOR(j, 0, n - 1)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:140:3: note: in expansion of macro 'FOR'
  140 |   FOR(i, 0, n - 1) {
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:146:4: note: in expansion of macro 'FOR'
  146 |    FOR(j, 0, sz(nodes) - 2) ans[nodes[j]][nodes[j + 1]] = ans[nodes[j + 1]][nodes[j]] = 1;
      |    ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:152:2: note: in expansion of macro 'FOR'
  152 |  FOR(i, 0, n - 1) {
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:156:3: note: in expansion of macro 'FOR'
  156 |   FOR(j, 0, sz(cc[cnt]) - 2) ans[cc[cnt][j]][cc[cnt][j + 1]] = ans[cc[cnt][j + 1]][cc[cnt][j]] = 1;
      |   ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:158:2: note: in expansion of macro 'FOR'
  158 |  FOR(i, 1, cnt)
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:159:2: note: in expansion of macro 'FOR'
  159 |  FOR(j, 1, cnt) {
      |  ^~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:162:3: note: in expansion of macro 'EACH'
  162 |   EACH(x, cc[i])
      |   ^~~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:163:3: note: in expansion of macro 'EACH'
  163 |   EACH(y, cc[j])
      |   ^~~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:167:3: note: in expansion of macro 'EACH'
  167 |   EACH(x, cc[i])
      |   ^~~~
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:168:3: note: in expansion of macro 'EACH'
  168 |   EACH(y, cc[j])
      |   ^~~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:175:2: note: in expansion of macro 'FOR'
  175 |  FOR(i, 1, cnt) {
      |  ^~~
supertrees.cpp:27:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
supertrees.cpp:181:3: note: in expansion of macro 'FOR'
  181 |   FOR(j, 0, sz(nodes) - 2) {
      |   ^~~

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