Submission #1059764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059764		j_vdd16	Flights (JOI22_flights)	C++17	64 / 100	229 ms	3468 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;
    vi parents;
    vii inOut;
    int counter;

    constexpr int MAX = 15;

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

        int subtreeSize = 1;

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

            subtreeSize += dfs(child, node);
        }

        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 : adj[node]) {
            if (child == parents[node] || 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;
    void dfsID(int node, int parent, int specialIndex, int& count) {
        SetID(node, specialIndex * MAX + (count++));

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

            dfsID(child, node, specialIndex, count);
        }
    }
    void setIDS() {
        loop(i, specialIndices.size()) {
            int count = 0;
            dfsID(specialIndices[i], parents[specialIndices[i]], i, count);
        }
    }
    
}

void Init(int N, std::vector<int> U, std::vector<int> V) {
    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);
    parents = vi(n);
    counter = 0;
    inOut = vii(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() < 1024) {
        auto [size, node] = specialQueue.top();
        if (specialQueue.size() >= (2 * n) / MAX) break;

        specialQueue.pop();

        split(node);
    }

    while (specialQueue.size()) {
        specialIndices.push_back(specialQueue.top().second);
        specialQueue.pop();
    }

    //maxGroupSize = 0;
    for (int x : specialIndices) {
        maxGroupSize = max(maxGroupSize, subtreeSizes[x]);
    }
    cerr << "Max group size: " << maxGroupSize << 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 : adj[node]) {
            if (child == parents[node] || 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 : adj[node]) {
            if (child == parents[node] || 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);
    
    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;
}

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

}

std::string SendB(int N, int X, int Y) {
    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;
                }
            }
        }
    }

    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;
    
    parse(children1, parents1, adj1, T, i);
    if (x / (MAX) == y / (MAX)) {
        return distanceDfs(adj1, node1, -1, node2);
    }

    parse(children2, parents2, adj2, T, i);

    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:113:9: note: in expansion of macro 'loop'
  113 |         loop(i, specialIndices.size()) {
      |         ^~~~
Ali.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>)':
Ali.cpp:152:33: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  152 |         if (specialQueue.size() >= (2 * n) / MAX) break;
      |             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
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:152:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         while (i < T.size()) {
      |                ~~^~~~~~~~~~

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