Submission #1253671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253671		zipdang04	Migrations (IOI25_migrations)	C++20	23 / 100	29 ms	1076 KiB

migrations

#include "migrations.h"

#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T> using PQMax = priority_queue<T>;
template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
    if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
    if (b < a) a = b;
}
template <class T>
void read(T &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    while (c != '-' && !isalnum(c)) c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
    read(a);
    read(args...);
}

/*
struct Node
{
    int node, len;
    Node() {node = len = 0;}
    Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/

#define fi first
#define se second

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define REV(type, i, b, a) for(type i = (b); i >= (a); i--)

#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define log2(n) (31 - __builtin_clz(n))
#define log2ll(n) (63 - __builtin_clzll(n))
#define CURRENT_TIMESTAMP chrono::steady_clock::now().time_since_epoch().count()
#define randomize mt19937_64 mt(CURRENT_TIMESTAMP)

#define MAX 10'005
#define BIT 14
#define MOD 1000000007

int n, p[MAX];

namespace Research {
    int lvl[MAX + 1] = {};
    struct LCA {
        int rmq[BIT + 1][MAX + 1] = {};
        void build(int node) {
            rmq[0][node] = p[node];
            FOR(int, bit, 1, BIT)
                rmq[bit][node] = rmq[bit-1][rmq[bit-1][node]];
        }

        int jump(int u, int dist) {
            for (int bit = 0; dist > 0; bit++, dist >>= 1)
                if (dist & 1)
                    u = rmq[bit][u];
            return u;
        }
        int getLCA(int u, int v) {
            if (lvl[u] > lvl[v]) swap(u, v);
            v = jump(v, lvl[v] - lvl[u]);
            if (u == v) return u;

            FOR(int, bit, 1, BIT)
                if (rmq[bit][u] != rmq[bit][v])
                    u = rmq[bit][u], v = rmq[bit][v];
            return p[u];
        }
        int calDist(int u, int v) {
            int p = getLCA(u, v);
            return lvl[u] + lvl[v] - lvl[p] * 2;
        }
    } lca;

    int one = 0, two = 1, dist = 1;
    int addNode(int node, int parent) {
        p[node] = parent; lvl[node] = lvl[parent] + 1;
        lca.build(node);
        if (node <= 1) return 0;

        // either one or two
        int dist1 = lca.calDist(one, node);
        int dist2 = lca.calDist(two, node);
        // cerr << node << '|' << one << ' ' << two << '|' << lca.getLCA(one, node) << ' ' << lca.getLCA(two, node) << '|' << dist1 << ' ' << dist2 << '\n';
        int ans = (dist1 > dist2) ? 1 : 2;
        int newDist = (ans == 1) ? dist1 : dist2;

        if (newDist <= dist) return 0;
        dist = newDist; one = (ans == 1) ? one : two;
        two = node; return ans;
    }

    #define START 9981
    int oldOne, oldTwo;
    int calMessage(int turn, int state) {
        if (turn < START) return 0;
        
        if (turn == START) {
            oldOne = one, oldTwo = two;
        }
        switch (turn) {
            case START: 
                return oldOne / 100;
            case START+1: 
                return oldOne % 100;
            case START+2: 
                return oldTwo / 100;
            case START+3: 
                return oldTwo % 100;
            default:
                break;
        }

        if (turn == START + 4) {
            // cerr << "START + 4" << ' ' << oldOne << ' ' << oldTwo << ' ' << one << ' ' << two << '\n';
            if (oldOne == one and oldTwo == two) return 0;
            // cerr << "still\n";
            if (one >= START) {
                int b0 = one - START, b1 = two - START;
                return (1 << b0) | (1 << b1);
            }
            int signal = 1 << 5;
            int oldNode = (one == oldOne) ? 1 : 2;
            int newNode = two - START;
            return signal | (oldNode << 3) | newNode;
        }

        return state;
    }
}
int send_message(int N, int i, int Pi) {
    int state = Research::addNode(i, Pi);
    if (i == 1) { n = N; return 0; }
    int message = Research::calMessage(i, state);
    // if (i >= START) cerr << i << ' ' << message << '\n';
    return message;
}

namespace Museum {
    int one = 0, two = 0;
    void build(int turn, int message) {
        // cerr << turn << ' ' << message << '\n';
        if (turn < START) return;
        switch (turn) {
            case START:
                one += 100 * message;
                return;
            case START + 1:
                one += message;
                return;
            case START + 2:
                two += 100 * message;
                return;
            case START + 3:
                two += message;
                return;
            case START + 4: {
                // cerr << "START + 4 " <<  bitset<6>(message) << '\n';
                if (message == 0) return;
                if (message >> 5) {
                    int newNode = message & 0b111; message >>= 3;
                    int oldNode = message & 0b11;

                    oldNode = (oldNode == 1) ? one : two;
                    newNode += START;
                    one = oldNode, two = newNode;
                    return;
                }

                one = 0, two = 0;
                FOR(int, i, 0, 4) if (testBit(message, i)) {
                    if (one) two = START + i;
                    else one = START + i;
                }
            } return;
            default:
                if (message == 0);
                else {
                    one = (message == 1) ? one : two;
                    two = turn;
                }
        }
    }
}

std::pair<int, int> longest_path(std::vector<int> S) {
    n = 1 + (int) S.size();
    FOR(int, i, 1, n-1)
        Museum::build(i, S[i]);
    return {Museum::one, Museum::two};
}

Compilation message (stderr)

migrations.cpp: In function 'void read(T&)':
migrations.cpp:30:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |     register int c;
      |                  ^

• Subtask 0: 0 / 0
• Subtask 1: 23 / 30
• Subtask 2: 0 / 70