Submission #1302854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302854		nikoloz-ch	Migrations (IOI25_migrations)	C++20	0 / 100	1035 ms	1136 KiB

migrations

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

static const int MAXN = 10005;
static vector<int> adj[MAXN];
static int pu = -1, pv = -1, t[4] = {0,0,0,0}, r[4] = {0,0,0,0}, s = -1, c = -1;
static bool p = false, h = false, e = true;

static vector<int> bfs_from(int src, int N) {
    vector<int> dist(N, -1);
    if(src < 0 or src >= N) return dist;
    queue<int> q;dist[src] = 0;q.push(src);
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : adj[v]) {
            if (to >= 0 and to < N and dist[to] == -1) {
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }
    return dist;
}

static pair<int,int> recompute_diameter(int N){
    int start = 0;
    auto d0 = bfs_from(start, N);
    bool any = false;
    for (int i = 0; i < N; ++i) if (d0[i] != -1) { any = true; break; }
    if (!any) return {0,0};
    int u = start;
    for (int i = 0; i < N; ++i) if (d0[i] > d0[u]) u = i;
    auto du = bfs_from(u, N);
    int v = u;
    for (int i = 0; i < N; ++i) if (du[i] > du[v]) v = i;
    return {u, v};
}

int send_message(int N, int i, int Pi){
    if(Pi >= 0){
        if(i >= 0 and i < N and Pi >= 0 and Pi < N){
            adj[i].push_back(Pi);adj[Pi].push_back(i);
        }
    }
    auto pr = recompute_diameter(N);
    int u = pr.first, v = pr.second;
    if(u != pu or v != pv){
        pu = u; pv = v;
        t[0] = u % 10;t[1] = (u / 10) % 10;t[2] = v % 10;t[3] = (v / 10) % 10;
        int a = 0;
        for(int i = 0; i < 4; i++){
            a += (t[i] + 3) / 4;
        }
        int nmsg = 2 * a;
        if(nmsg > 24) nmsg = 24;
        int sched = N - nmsg;
        if (sched <= i) sched = i+1;
        s = sched;p = true;h = false;
        return 0;
    }
    if(p and i < s){
        return 0;
    }
    if(p and i >= s and !h){
        for(int i = 0; i < 4; i++) r[i] = t[i];
        h = true;p = false;e = true;c = -1;
        return 0;
    }
    if(h){
        if(e){
            int pos = -1;
            for(int i = 0; i < 4; i++) if (r[i] > 0){pos = i; break;}
            if(pos == -1){
                h = false;
                return 0;
            }
            c = pos;e = false;
            return (c + 1);
        }else{
            int pos = c;
            if(pos < 0 or pos >= 4){
                e = true;
                return 0;
            }
            int step = min(4, r[pos]);
            r[pos] -= step;
            e = true;
            bool tt = false;
            for(int i = 0; i < 4; i++) if(r[i] > 0){tt = true; break;}
            if(!tt) h = false;
            return step;
        }
    }

    return 0;
}

pair<int,int> longest_path(vector<int> S){
    int n = S.size(); 
    bool tr = false, used = false;
    array<int,4> num = {0,0,0,0};
    pair<int,int> ls = {0,0};
    bool bl = true;
    int ans = -1;

    for(int i = 0; i < n; ++i){
        int x = S[i];

        if(x == 0){
            if(tr && used){
                int u = num[0] + 10 * num[1];
                int v = num[2] + 10 * num[3];
                ls = {u, v};
            }
            tr = true;
            bl = true;
            ans = -1;
            used = false;
            num = {0,0,0,0};
            continue;
        }

        if(!tr) continue;

        if(x < 1 or x > 4){
            bl = true;
            ans = -1;
            continue;
        }

        if(bl){
            ans = x - 1;
            bl = false;
        } else {
            if(ans >= 0 and ans < 4){
                num[ans] += x;
                used = true;
            }
            bl = true;
            ans = -1;
        }
    }

    if(tr && used){
        int u = num[0] + 10 * num[1];
        int v = num[2] + 10 * num[3];
        ls = {u, v};
    }

    return ls;
}

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