# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1062175 | j_vdd16 | Flights (JOI22_flights) | C++17 | 255 ms | 3924 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |