제출 #636381

#제출 시각아이디문제언어결과실행 시간메모리
636381ghostwriter슈퍼트리 잇기 (IOI20_supertrees)C++14
컴파일 에러
0 ms0 KiB
#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 N = 1005; int P[N][N], adj[N][N], p1[N], s[N], c[N], cnt = 0; bitset<N> d[N]; vi nodes, cc[N]; 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; EACH(v, adj[u]) { if (c[v]) continue; dfs2(v); } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); 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<N> 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 (!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; ans[cc[cnt][0]][cc[cnt].back()] = ans[cc[cnt].back()][cc[cnt][0]] = 1; } memset(c, 0, sizeof c); 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; } 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) ans[nodes[j]][nodes[j + 1]] = ans[nodes[j + 1]][nodes[j]] = 1; } build(ans); return 1; }

컴파일 시 표준 에러 (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:56:12: error: 'n' was not declared in this scope
   56 |  FOR(v, 0, n - 1) {
      |            ^
supertrees.cpp:27:50: note: in definition of macro 'FOR'
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                                                  ^
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:64:12: error: 'n' was not declared in this scope
   64 |  FOR(v, 0, n - 1) {
      |            ^
supertrees.cpp:27:50: note: in definition of macro 'FOR'
   27 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                                                  ^
supertrees.cpp: In function 'void dfs2(int)':
supertrees.cpp:29:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   29 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
supertrees.cpp:71:2: note: in expansion of macro 'EACH'
   71 |  EACH(v, adj[u]) {
      |  ^~~~
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:83:2: note: in expansion of macro 'FOR'
   83 |  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:84:2: note: in expansion of macro 'FOR'
   84 |  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:87:2: note: in expansion of macro 'FOR'
   87 |  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:88:2: note: in expansion of macro 'FOR'
   88 |  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:93:2: note: in expansion of macro 'EACH'
   93 |  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:94:2: note: in expansion of macro 'EACH'
   94 |  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:98:3: note: in expansion of macro 'FOR'
   98 |   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:103:2: note: in expansion of macro 'FOR'
  103 |  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:104:2: note: in expansion of macro 'FOR'
  104 |  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:106:2: note: in expansion of macro 'FOR'
  106 |  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:107:2: note: in expansion of macro 'FOR'
  107 |  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:115:2: note: in expansion of macro 'EACH'
  115 |  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:116:2: note: in expansion of macro 'EACH'
  116 |  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:120:3: note: in expansion of macro 'FOR'
  120 |   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:124:3: note: in expansion of macro 'FOR'
  124 |   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:125:3: note: in expansion of macro 'FOR'
  125 |   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:133:2: note: in expansion of macro 'FOR'
  133 |  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:134:2: note: in expansion of macro 'FOR'
  134 |  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:138:3: note: in expansion of macro 'FOR'
  138 |   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:144:4: note: in expansion of macro 'FOR'
  144 |    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:150:2: note: in expansion of macro 'FOR'
  150 |  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:154:3: note: in expansion of macro 'FOR'
  154 |   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:174:2: note: in expansion of macro 'FOR'
  174 |  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:180:3: note: in expansion of macro 'FOR'
  180 |   FOR(j, 0, sz(nodes) - 2) ans[nodes[j]][nodes[j + 1]] = ans[nodes[j + 1]][nodes[j]] = 1;
      |   ^~~