Submission #1262117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262117		HossamHero7	Migrations (IOI25_migrations)	C++20	80.17 / 100	1343 ms	1092 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #ifndef ONLINE_JUDGE
// #include "grader.cpp"
// #endif
const int N = 1e4;
int p[N];
int lst = -1;
vector<int> adj[N];
int dep[N];
int x,y,xx,yy;
int cur = 0;
int bfs(int src){
    queue<int> q;
    vector<bool> vis(N);
    for(int i=0;i<N;i++) dep[i] = 0;
    q.push(src);
    vis[src] = 1;
    while(q.size()){
        int node = q.front();       q.pop();
        for(auto ch : adj[node]){
            if(vis[ch]) continue;
            q.push(ch);
            vis[ch] = 1;
            dep[ch] = dep[node] + 1;
        }
    }
    pair<int,int> mx{-1,0};
    for(int j=0;j<N;j++) {
        if(dep[j] > mx.first) mx = {dep[j] , j};
        else if(dep[j] == mx.first && (j == xx || j == yy)) mx = {dep[j] , j};
        else if(dep[j] == mx.first && (j == cur)) mx = {dep[j] , j};
    }
    return mx.second;
}
pair<int,int> calc(){
    int tmp = bfs(0);
    pair<int,int> p{tmp,bfs(tmp)};
    if(tmp == yy || p.second == xx) swap(p.first,p.second);
    return p;
}
int changed_x = 0 , changed_y = 0;
int send_message(int n, int i, int Pi) {
    adj[i].push_back(Pi);
    adj[Pi].push_back(i);
    vector<ll> powe(8);
    powe[0] = 1;
    for(int j=1;j<=7;j++) powe[j] = powe[j-1] * 4;
    // cout<<i<<": "<<x<<' '<<y<<endl;
    if(i >= n - 21){
        int it = i - (n-21);
        cur = i;
        auto [xx_,yy_] = calc();
        xx = xx_;
        yy = yy_;
        // cout<<i<<" -> "<<xx<<' '<<yy<<endl;
        if(it < 8) y = yy;
        if(it < 7){
            if(xx == x) return (x / powe[it]) % 4;
            else return x = xx , 4;
        }
        else {
            it -= 7;
            if(it % 2 == 0){
                if(y == yy) return (y / powe[it>>1]) % 4;
                else return y = yy , 4;
            }
            else {
                if(xx == i) return x = xx, 0;
                else if(xx == i-1 && yy != i) return x = xx , 1;
                else if(xx == i-1 && yy == i) return x = xx , y = yy , 2;
                else if(yy != i) return 3;
                else if(yy == i) return y = yy , 4;
            }
        }
    }
    else {
        auto [xx_,yy_] = calc();
        xx = xx_;
        yy = yy_;
        x = xx , y = yy;
    }
    return 0;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    vector<ll> powe(8);
    powe[0] = 1;
    for(int j=1;j<=7;j++) powe[j] = powe[j-1] * 4;
    int n = N;
    int x = 0 , y = 0;
    bool changed_x = 0 , changed_y = 0;
    for(int i=n-21;i<n;i++){
        int it = i - (n-21);
        if(it < 7){
            if(S[i] == 4) changed_x = 1 , x = i;
            else if(!changed_x){
                x += powe[it] * S[i];
            }
        }
        else {
            it -= 7;
            if(it % 2 == 0){
                if(S[i] == 4) changed_y = 1 , y = i;
                else if(!changed_y) y += powe[it>>1] * S[i];
            }
            else {
                if(S[i] == 0) x = i;
                else if(S[i] == 1) x = i - 1;
                else if(S[i] == 2) x = i - 1 , y = i , changed_y = 1;
                else if(S[i] == 3) continue;
                else y = i , changed_y = 1;
            }
        }
    }
    // cout<<x<<' '<<y<<endl;
    // bfs(x);
    // cout<<dep[y]<<endl;
    return {x,y};
}

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