Submission #1302872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302872		nikoloz-ch	이주 (IOI25_migrations)	C++20	0 / 100	1086 ms	1136 KiB

migrations

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

static const int MAXN = 10005;
static vector<int> adj[MAXN];
bool fn = false, kl = false;
static pair<int,int> ans = {-1,-1};
static bool tr = false;
static int D = 0;
int num = 10000;
vector<int> bfs(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 && to < N && dist[to] == -1){
                dist[to] = dist[v] + 1;
                q.push(to);
            }
        }
    }
    return dist;
}
int k = 10000;
int cnt(int n){
    int as = 0;
    while(n > 0){
        as += ((n % 10) + (n % 10) % 4)/4;
        n /= 10;
    }
    return as;
}
int send_message(int N, int i, int Pi){
    if(Pi >= 0){
        if (i >= 0 && i < N && Pi >= 0 && Pi < N) {
            adj[i].push_back(Pi);
            adj[Pi].push_back(i);
        }
    }
    int start = 0;auto d0 = bfs(start, N);int u = start;
    for(int x = 0; x < N; x++)if(d0[x] > d0[u]) u = x;
    auto du = bfs(u, N);int v = u;
    for(int x = 0; x < N; x++)if(du[x] > du[v]) v = x;
    pair<int,int> ns = {u, v};
    if(ns != ans){
        ans = ns;
        D = (du[v] >= 0 ? du[v] : 0);
        tr = true;
    }else{
        tr = false;
    }
    if(k > cnt(ns.second)) return 0;
    if(tr and k != cnt(ns.second)){
        kl = true;
        return 0;
    } else if(kl){
        return 1;
    } else if(fn){
        return 5;
    } else{
        int nt = num, pt = 0;
        while(ns.second % 10 == nt % 10){
            ns.second /= 10; nt /= 10; pt++;
        }
        if(ns.second % 10 - nt % 10 > 4){
            return 4;
            num += pow<int>(10,pt)*4;
        } else return (ns.second % 10 - nt % 10), num += pow<int>(10,pt)*4;;
    }
    k--;
}

pair<int,int> longest_path(vector<int> S){
    int ind = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] != 0){
            ind = i;
            break;
        }
    }
    int num = 10000, mod = ind % 2;
    for(int i = ind+1; i < S.size(); i++){
        if(S[i] == 0) return {0LL, i};
        if(i % 2 == mod){
            continue;
        } else{
            num += pow<int>(10,S[i-1])*S[i];
        }
    }
    return {0LL,num-10000LL};
}

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