| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1302870 | nikoloz-ch | 이주 (IOI25_migrations) | C++20 | 0 ms | 0 KiB |
#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
static 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};
}