Submission #1062181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062181		j_vdd16	Flights (JOI22_flights)	C++17	87 / 100	295 ms	4200 KiB

Ali

#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 = 1446;
    constexpr int BEST = (10000 + MAX_GROUP_COUNT - 1) / MAX_GROUP_COUNT;
    constexpr int MAX = 2 * ((10000 + MAX_GROUP_COUNT - 1) / 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;
}

Benjamin

#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 = 1446;
    constexpr int BEST = (10000 + MAX_GROUP_COUNT - 1) / MAX_GROUP_COUNT;
    constexpr int MAX = 2 * ((10000 + MAX_GROUP_COUNT - 1) / 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;
}

Compilation message (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()) {
      |                ~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 72 / 85