Submission #1060297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060297		j_vdd16	Flights (JOI22_flights)	C++17	15 / 100	226 ms	4244 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

#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 = 16;

    int dfs(int node, int parent) {
        inOut[node].first = counter++;

        int subtreeSize = 1;

        for (int child : adj[node]) {
            if (child == parent) continue;

            subtreeSize += dfs(child, node);
            children[node].push_back(child);
        }

        inOut[node].second = counter++;

        subtreeSizes[node] = subtreeSize;
        if (subtreeSize >= 10) {
            specialQueue.push({subtreeSize, node});
            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];
                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, cat2;
        if (relevant.size() == 1) {
            cat1 = catalanCompress(child0);
            cat2 = 0;
        }
        else {
            int child1 = relevant[1];
            if (subtreeSizes[child0] < subtreeSizes[child1]) 
                swap(children[node][0], children[node][1]);
                
            cat1 = catalanCompress(child0);
            cat2 = catalanCompress(child1);
        }

        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;

    int subtreeSize = dfs(root, root);
    if (!isSpecial[root]) {
        isSpecial[root] = true;
        specialQueue.push({subtreeSize + 1, root});
    }

    while (specialQueue.size() < min(1024, (2 * n) / 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 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];

    
    // string code1, code2;
    // treeCode(node1, code1);
    // treeCode(node2, code2);

    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 += "10";

        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 += "11";

        node2 = closest.first;
        while (closest.second) {
            if (closest.second % 2) 
                extra.push_back('1');
            else 
                extra.push_back('0');

            closest.second /= 2;
        }
    }
    else {
        extra.push_back('0');
    }

    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 = 16;

    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];
                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;// * 2;
    Y /= MAX;// * 2;
    //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 parse(vii& children, vi& parents, vvi& adj, const string& T, int& i) {
        children = { { -1, -1} };
        parents = { -1 };
        adj = vvi(1);

        int node = 0;
        while (true) {
            bool bit = T[i++] == '1';
        
            if (bit) {
                parents.push_back(node);
                adj.push_back({});
                children.push_back({ -1, -1 });
                int next = (int)parents.size() - 1;
                adj[node].push_back(next);
                adj[next].push_back(node);

                if (children[node].first == -1) {
                    children[node].first = next;
                }
                else {
                    children[node].second = next;
                }
                node = next;
            }
            else {
                if (parents[node] == -1) {
                    break;
                }

                node = parents[node];
                
                while (parents[node] != -1 && children[node].second >= 0)
                    node = parents[node];

                if (children[node].second >= 0 && parents[node] == -1) {
                    break;
                }
            }
        }
    }*/

    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 child0 = children[node][0];

        // int cat1, cat2;
        // if (children[node].size() == 1) {
        //     cat1 = catalanCompress(children[node][0]);
        //     cat2 = 0;
        // }
        // else {
        //     int child1 = children[node][0];
                
        //     cat1 = catalanCompress(child0);
        //     cat2 = catalanCompress(child1);
        // }

        // int size0 = subtreeSizes[child0];

        // int res = catPref2[subtreeSizes[node]][size0] + cat1 * catalan[subtreeSizes[node] - size0 - 1] + cat2;
        // return res;
    }
    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;
        }
    }
    
    //parse(children1, parents1, adj1, T, i);
    catalanDecompress(children1, parents1, adj1, T.substr(i, bitCount));
    i += bitCount;

    if (x / (MAX) == y / (MAX)) {
        return distanceDfs(adj1, node1, -1, node2);
    }

    //parse(children2, parents2, adj2, T, i);
    catalanDecompress(children2, parents2, adj2, T.substr(i, bitCount));
    i += bitCount;

    int start1 = 0, start2 = 0;
    if (T[i++] == '1') {
        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:119:9: note: in expansion of macro 'loop'
  119 |         loop(i, specialIndices.size()) {
      |         ^~~~
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:210: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]
  210 |     while (specialQueue.size() < min(1024, (2 * n) / 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:265:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |         while (i < T.size()) {
      |                ~~^~~~~~~~~~

Subtask 115 / 15

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 20 / 85

#	Verdict	Execution time	Memory	Grader output
Fetching results...