제출 #1062175

#제출 시각아이디문제언어결과실행 시간메모리
1062175j_vdd16Flights (JOI22_flights)C++17
87 / 100
255 ms3924 KiB
#include "Ali.h" #include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; namespace { int n; vvi adj; priority_queue<ii> specialQueue; vi specialIndices; vi subtreeSizes; vb isSpecial; vii inOut; vvi children; int counter; constexpr int MAX_GROUP_COUNT = 1400; constexpr int BEST = 10000 / MAX_GROUP_COUNT; constexpr int MAX = 2 * (10000 / MAX_GROUP_COUNT) - 1; // ii divideDfs(int node, int parent, int splitLim) { // int subtreeSize = 1; // int count = 0; // for (int child : adj[node]) { // if (child == parent) continue; // ii res = divideDfs(child, node, splitLim); // subtreeSize += res.first; // count += res.second; // } // if (subtreeSize >= splitLim) { // count++; // subtreeSize = 0; // } // return { subtreeSize, count }; // } int dfs(int node, int parent, int splitLim) { inOut[node].first = counter++; int subtreeSize = 1; for (int child : adj[node]) { if (child == parent) continue; subtreeSize += dfs(child, node, splitLim); children[node].push_back(child); } inOut[node].second = counter++; subtreeSizes[node] = subtreeSize; if (subtreeSize > MAX) { isSpecial[children[node][0]] = true; isSpecial[children[node][1]] = true; subtreeSizes[node] = 1; subtreeSize = 1; } else if (subtreeSize >= splitLim) { isSpecial[node] = true; subtreeSize = 0; } return subtreeSize; } void split(int node) { vi possible; for (int child : children[node]) { if (isSpecial[child]) continue; possible.push_back(child); } int child; if (possible.size() == 2) { if (subtreeSizes[possible[0]] > subtreeSizes[possible[1]]) { child = possible[0]; } else { child = possible[1]; } } else { child = possible[0]; } isSpecial[child] = true; specialQueue.push({subtreeSizes[child], child}); subtreeSizes[node] -= subtreeSizes[child]; specialQueue.push({subtreeSizes[node], node}); } bool isAncestor(int a, int b) { return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second; } int maxGroupSize = 0; int minGroupSize = INT_MAX; void dfsID(int node, int specialIndex, int& count) { SetID(node, specialIndex * MAX + (count++)); if (children[node].size() == 2) { if (subtreeSizes[children[node][0]] < subtreeSizes[children[node][1]]) swap(children[node][0], children[node][1]); } for (int child : children[node]) { if (isSpecial[child]) continue; dfsID(child, specialIndex, count); } } void setIDS() { loop(i, specialIndices.size()) { int count = 0; dfsID(specialIndices[i], i, count); } } vi catalan, catPref; vvi catPref2; void initCatalan() { catalan = vi(MAX + 1); catalan[0] = 1; catPref = vi(MAX + 2); catPref2 = vvi(MAX + 1, vi(MAX + 1)); for (int i = 1; i <= MAX; i++) { for (int j = (i - 1) / 2; j >= 0; j--) { catPref2[i][i - 1 - j] = catalan[i]; if (i - 1 - j >= BEST || j >= BEST) continue; if (i - 1 - j == j) { catalan[i] += catalan[i - 1 - j] * catalan[j]; //catalan[i] += catalan[j] * (catalan[j] + 1) / 2; } else { catalan[i] += catalan[i - 1 - j] * catalan[j]; } } catPref[i] = catPref[i - 1] + catalan[i - 1]; //pref2[i][j] = cat[j - k] * cat[i - 1 - (j - k)] } catPref[MAX + 1] = catPref[MAX] + catalan[MAX]; } int catalanCompress(int node) { int childCount = 0; vi relevant; for (int child : children[node]) { if (isSpecial[child]) continue; childCount++; relevant.push_back(child); } if (relevant.size() == 0) return 0; int child0 = relevant[0]; int cat1 = catalanCompress(child0); int cat2 = 0; if (relevant.size() == 2) { cat2 = catalanCompress(relevant[1]); } int size0 = subtreeSizes[child0]; int res = catPref2[subtreeSizes[node]][size0] + cat1 * catalan[subtreeSizes[node] - size0 - 1] + cat2; return res; } } void Init(int N, std::vector<int> U, std::vector<int> V) { initCatalan(); n = N; adj = vvi(n); loop(i, n - 1) { adj[U[i]].push_back(V[i]); adj[V[i]].push_back(U[i]); } specialIndices = vi(); subtreeSizes = vi(n); isSpecial = vb(n); counter = 0; inOut = vii(n); children = vvi(n); int root = 0; if (adj[0].size() > 2) { loop(i, n) { if (adj[i].size() <= 2) root = i; } } cerr << "Root: " << root << endl; dfs(root, root, BEST); if (!isSpecial[root]) { isSpecial[root] = true; } loop(i, n) { if (isSpecial[i]) { specialQueue.push({subtreeSizes[i], i}); } } while (specialQueue.size() < min(MAX_GROUP_COUNT, (2 * n + 20) / MAX)) { auto [size, node] = specialQueue.top(); specialQueue.pop(); split(node); } while (specialQueue.size()) { specialIndices.push_back(specialQueue.top().second); specialQueue.pop(); } for (int x : specialIndices) { maxGroupSize = max(maxGroupSize, subtreeSizes[x]); minGroupSize = min(minGroupSize, subtreeSizes[x]); } cerr << "Max group size: " << maxGroupSize << endl; cerr << "Min group size: " << minGroupSize << endl; setIDS(); } namespace { int distanceDfs(int node, int parent, int goal) { if (node == goal) return 0; for (int child : adj[node]) { if (child == parent) continue; int res = distanceDfs(child, node, goal); if (res >= 0) return res + 1; } return -1; } void treeCode(int node, string& code) { int childCount = 0; for (int child : children[node]) { if (isSpecial[child]) continue; childCount++; code.push_back('1'); treeCode(child, code); } if (childCount < 2) code.push_back('0'); } ii closestLeafDfs(int node, const vi& distances, int& closestCounter) { ii best = { node, closestCounter++ }; for (int child : children[node]) { if (isSpecial[child]) continue; ii res = closestLeafDfs(child, distances, closestCounter); if (distances[res.first] < distances[best.first]) best = res; } return best; } void setDistances(int node, int parent, int distance, vi& distances) { distances[node] = distance; for (int child : adj[node]) { if (child == parent) continue; setDistances(child, node, distance + 1, distances); } } } std::string SendA(std::string S) { //return max 24 is optimal int inCode = 0; loop(i, 20) { if (S[i] == '1') inCode += 1 << i; } int idx1 = 0; while ((idx1 + 1) * idx1 / 2 <= inCode) idx1++; idx1--; int idx2 = inCode - (idx1 + 1) * idx1 / 2; // int idx1 = 0, idx2 = 0; // loop(i, 10) { // idx1 += (S[i] == '1') * (1 << i); // } // loop(i, 10) { // idx2 += (S[i + 10] == '1') * (1 << i); // } int node1 = specialIndices[idx1]; int node2 = specialIndices[idx2]; int bitCount = 0; { int count = catPref[MAX + 1]; while (count) { bitCount++; count /= 2; } } string code1(bitCount, '0'), code2(bitCount, '0'); { int cat1 = catPref[subtreeSizes[node1]] + catalanCompress(node1); int cat2 = catPref[subtreeSizes[node2]] + catalanCompress(node2); loop(i, bitCount) { if (cat1 & (1 << i)) code1[i] = '1'; if (cat2 & (1 << i)) code2[i] = '1'; } } cerr << "Code 1: " << code1 << endl; cerr << "Code 2: " << code2 << endl; if (node1 == node2) { int dist = distanceDfs(node1, -1, node2); string result(14, '0'); loop(i, 14) { if (dist & (1 << i)) result[i] = '1'; } return result + code1; } string extra; if (isAncestor(node1, node2)) { vi distances(n); setDistances(node2, -1, 0, distances); int closestCounter = 0; ii closest = closestLeafDfs(node1, distances, closestCounter); extra += "0"; node1 = closest.first; while (closest.second) { if (closest.second % 2) extra.push_back('1'); else extra.push_back('0'); closest.second /= 2; } } else if (isAncestor(node2, node1)) { vi distances(n); setDistances(node1, -1, 0, distances); int closestCounter = 0; ii closest = closestLeafDfs(node2, distances, closestCounter); extra += "1"; node2 = closest.first; while (closest.second) { if (closest.second % 2) extra.push_back('1'); else extra.push_back('0'); closest.second /= 2; } } int dist = distanceDfs(node1, -1, node2); string result(14, '0'); loop(i, 14) { if (dist & (1 << i)) result[i] = '1'; } return result + code1 + code2 + extra; }
#include "Benjamin.h" #include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; namespace { int x, y; constexpr int MAX_GROUP_COUNT = 1400; constexpr int BEST = 10000 / MAX_GROUP_COUNT; constexpr int MAX = 2 * (10000 / MAX_GROUP_COUNT) - 1; vi catalan, catPref; vvi catPref2; void initCatalan() { catalan = vi(MAX + 1); catalan[0] = 1; catPref = vi(MAX + 2); catPref2 = vvi(MAX + 1, vi(MAX + 1)); for (int i = 1; i <= MAX; i++) { for (int j = (i - 1) / 2; j >= 0; j--) { catPref2[i][i - 1 - j] = catalan[i]; if (i - 1 - j >= BEST || j >= BEST) continue; if (i - 1 - j == j) { catalan[i] += catalan[i - 1 - j] * catalan[j]; //catalan[i] += catalan[j] * (catalan[j] + 1) / 2; } else { catalan[i] += catalan[i - 1 - j] * catalan[j]; } } catPref[i] = catPref[i - 1] + catalan[i - 1]; //pref2[i][j] = cat[j - k] * cat[i - 1 - (j - k)] } catPref[MAX + 1] = catPref[MAX] + catalan[MAX]; } } std::string SendB(int N, int X, int Y) { initCatalan(); cerr << "X: " << X << ", Y: " << Y << endl; x = X; y = Y; X /= MAX; Y /= MAX; if (X < Y) { swap(X, Y); swap(x, y); } /* 0, 0 = 0 1, 0 = 1 1, 1 = 2 2, 0 = 3 2, 1 = 4 */ int out = ((X + 1) * X) / 2 + Y; string outStr(20, '0'); loop(i, 20) { if (out & (1 << i)) outStr[i] = '1'; } return outStr; //log2(N) < 14 // string out(20, '0'); // loop(i, 10) { // if (X & (1 << i)) out[i] = '1'; // } // loop(i, 10) { // if (Y & (1 << i)) out[10 + i] = '1'; // } // return out; } namespace { void catalanDecompressDfs(int node, vii& children, vi& parents, vvi& adj, int code, int size) { int size0 = (size - 1) / 2; for (; size0 < size; size0++) { if (catPref2[size][size0] > code) break; } size0--; code -= catPref2[size][size0]; int code0 = code / catalan[size - size0 - 1]; int code1 = code % catalan[size - size0 - 1]; if (size0 == 0) return; int child0 = (int)children.size(); children[node].first = child0; adj.push_back({}); adj[child0] = { node }; adj[node].push_back(child0); children.push_back({-1, -1}); parents.push_back(node); catalanDecompressDfs(child0, children, parents, adj, code0, size0); if (size - size0 - 1 > 0) { int child1 = (int)children.size(); children[node].second = child1; adj.push_back({}); adj[children.size()] = { node }; adj[node].push_back(child1); children.push_back({-1, -1}); parents.push_back(node); catalanDecompressDfs(child1, children, parents, adj, code1, size - size0 - 1); } // int res = catPref2[subtreeSizes[node]][size0] + cat1 * catalan[subtreeSizes[node] - size0 - 1] + cat2; } void catalanDecompress(vii& children, vi& parents, vvi& adj, const string& T) { int code = 0; loop(i, (int)T.size()) { if (T[i] == '1') code += 1 << i; } int nodeCount = 1; while (code >= catPref[nodeCount]) nodeCount++; nodeCount--; code -= catPref[nodeCount]; children = { {-1, -1} }; parents = { 0 }; adj = { {} }; catalanDecompressDfs(0, children, parents, adj, code, nodeCount); } int distanceDfs(const vvi& adj, int node, int parent, int goal) { if (node == goal) return 0; for (int child : adj[node]) { if (child == parent) continue; int res = distanceDfs(adj, child, node, goal); if (res >= 0) return res + 1; } return -1; } } int Answer(std::string T) { cerr << "T: " << T << endl; int dist = 0; int i = 0; for (; i < 14; i++) { if (T[i] == '1') dist += (1 << i); } cerr << "Dist: " << dist << endl; cerr << "Rest: " << T.substr(i) << endl; int node1 = x % (MAX); int node2 = y % (MAX); vii children1, children2; vi parents1, parents2; vvi adj1, adj2; int bitCount = 0; { int count = catPref[MAX + 1]; while (count) { bitCount++; count /= 2; } } catalanDecompress(children1, parents1, adj1, T.substr(i, bitCount)); i += bitCount; if (x / MAX == y / MAX) { return distanceDfs(adj1, node1, -1, node2); } catalanDecompress(children2, parents2, adj2, T.substr(i, bitCount)); i += bitCount; int start1 = 0, start2 = 0; if (i < (int)T.size()) { bool nextBit = T[i++] == '1'; int closestIdx = 0; int startIdx = i; while (i < T.size()) { closestIdx += (T[i] == '1') * (1 << (i - startIdx)); i++; } if (nextBit) { start2 = closestIdx; } else { start1 = closestIdx; } } dist += distanceDfs(adj1, start1, -1, node1); dist += distanceDfs(adj2, start2, -1, node2); return dist; }

컴파일 시 표준 에러 (stderr) 메시지

Ali.cpp: In function 'void {anonymous}::setIDS()':
Ali.cpp:19:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
Ali.cpp:146:9: note: in expansion of macro 'loop'
  146 |         loop(i, specialIndices.size()) {
      |         ^~~~
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:244:32: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  244 |     while (specialQueue.size() < min(MAX_GROUP_COUNT, (2 * n + 20) / MAX)) {
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'int Answer(std::string)':
Benjamin.cpp:238:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |         while (i < T.size()) {
      |                ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...