Submission #1302285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302285		Valaki2	Migrations (IOI25_migrations)	C++20	79.12 / 100	42 ms	2164 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int big_n = 1e4;
const int bitcnt_1 = 21;
const int bitcnt_2 = 14;

int n;
vector<int> par;
vector<vector<int> > graph;
vector<vector<int> > children;

int A, B;
int diam;

// maybe bigger is not enough, first part has to be bigger as well?
// so that negative .se; etc.

pii dfs_furthest(int cur, int pr) {
    pii res = mp(0, cur);
    for(int nei : graph[cur]) {
        if(nei != pr) {
            pii this_res = dfs_furthest(nei, cur);
            this_res.fi++;
            res = max(res, this_res);
        }
    }
    return res;
}

int dist(int cur, int pr, int goal) {
    if(cur == goal) {
        return 0;
    }
    int res = 1e5;
    for(int nei : graph[cur]) {
        if(nei != pr) {
            res = min(res, dist(nei, cur, goal) + 1);
        }
    }
    return res;
}

void init() {
    par.assign(big_n, -1);
    graph.resize(big_n);
    children.resize(big_n);
}

signed send_message(signed N, signed i, signed Pi) {
    n = i + 1;
    if(n == 2) {
        init();
    }
    par[i] = Pi;
    graph[i].pb(par[i]);
    graph[par[i]].pb(i);
    children[par[i]].pb(i);
    int pos = bitcnt_1 - (big_n - n + 1);
    if(pos < 0) {
        return 0;
    }
    if(pos == 0) {
        pii deepest = dfs_furthest(0, -1);
        A = deepest.se;
        deepest = dfs_furthest(A, -1);
        B = deepest.se;
        diam = deepest.fi;
    }
    if(pos < 7) {
        pii deepest = dfs_furthest(i, -1);
        if(deepest.fi > diam && dist(i, -1, A) <= diam) {
            A = i;
            diam++;
            return 4;
        } else {
            if(deepest.fi > diam) {
                diam++;
            }
            return (A >> (2 * pos)) & 3;
        }
    }
    pos -= 7;
    pii deepest = dfs_furthest(i, -1);
    if(deepest.fi <= diam) {
        return (B >> pos) & 1;
    }
    if(dist(i, -1, A) <= diam) {
        // A valtozik
        A = i;
        diam++;
        return ((B >> pos) & 1) + 2;
    } else {
        // B valtozik
        B = i;
        diam++;
        return 4;
    }
    /*if (i == 1)
        return 10;
    else if (i == 2)
        return 20;
    else if (i == 3)
        return 30;
    else
        return 0;*/
}

pair<signed, signed> longest_path(vector<signed> S) {
    int A = 0, B = 0;
    bool A_set = false, B_set = false;
    for(int i = big_n - bitcnt_1; i < big_n - bitcnt_2; i++) {
        if(S[i] == 4) {
            A_set = true;
            A = i;
        }
    }
    for(int i = big_n - bitcnt_2; i < big_n; i++) {
        if(S[i] >= 2 && S[i] <= 3) {
            A_set = true;
            A = i;
        }
    }
    if(!A_set) {
        int pos = 1;
        for(int i = big_n - bitcnt_1; i < big_n - bitcnt_2; i++) {
            A += pos * S[i];
            pos *= 4;
        }
    }
    for(int i = big_n - bitcnt_2; i < big_n; i++) {
        if(S[i] == 4) {
            B_set = true;
            B = i;
        }
    }
    if(!B_set) {
        int pos = 1;
        for(int i = big_n - bitcnt_2; i < big_n; i++) {
            B += pos * (S[i] % 2);
            pos *= 2;
        }
    }
    /*for(int i = 0; i < 6; i++) {
        for(int j = 0; j < 6; j++) {
            cout << dist(i, -1, j) << " ";
        }
        cout << "\n";
    }*/
    //cout << overall_best.fi << " " << overall_best.se << "\n";
    return mp(A, B);
    //return {0, 3};
}

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