| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1255094 | tosivanmak | 이주 (IOI25_migrations) | C++20 | 0 ms | 0 KiB |
#include "migrations.h"
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll dep[10005];
ll maxdep=0; ll nd;
vector<ll>btsmol,btbig;
vector<ll>adj[10005];
vector<ll> conv(ll x){
vector<ll>v;
for(int i=0;i<=13;i++){
if(x&(1LL<<i)){
v.push_back(1);
}
else{
v.push_back(0);
}
}
return v;
}
// N-i<=19
// 10000 9981
// 9981 to 9999 19 information
void dfs(ll s){
vis[s]=1;
for(auto& u: adj[s]){
if(!vis[u]){
dep[u]=dep[s]+1;
dfs(u);
}
}
}
pair<ll,ll>pr;
ll oris,orib;
int send_message(int N, int id, int Pi) {
if(N-id>28){adj[id].push_back(Pi); adj[Pi].push_back(id);return 0;}
if(N-id==28){
dfs(0);
ll maxi=0; ll nd;
for(int i=0;i<id;i++){
if(dep[i]>maxi){
maxi=dep[i]; nd=i;
}
}
for(int i=0;i<id;i++)dep[i]=0,vis[i]=0;
dfs(nd);
ll store=nd;
maxi=0; nd=0;
for(int i=0;i<id;i++){
if(dep[i]>maxi){
maxi=dep[i]; nd=i;
}
}
pr={min(store,nd),max(store,nd)};
btsmol=conv(pr.first); btbig=conv(pr.second);
oris=pr.first,orib=pr.second;
for(int i=0;i<id;i++){
vis[i]=0; dep[i]=0;
}
}
adj[id].push_back(Pi); adj[Pi].push_back(id);
dfs(pr.first); ll val1=dep[id]; ll comp1=dep[pr.second];
for(int i=0;i<id;i++){
vis[i]=0; dep[i]=0;
}
dfs(pr.second); ll val2=dep[id]; ll comp2=dep[pr.first];
for(int i=0;i<id;i++)vis[i]=0,dep[i]=0;
if(pr.first>=9972&&pr.second>=9972){
if(val1>comp1){
// replace big
pr.second=id;
return 2;
}
else if(val2>comp2){
// replace small
pr.first=pr.second; pr.second=id;
return 1;
}
else{
// not replace
return 0;
}
}
else if(pr.first==oris){
if(val1>comp1){
// replace big
pr.second=id;
if(id>=9972&&id<=9985){
// sending small
return 2+btsmol[id-9972];
}
else{
// sending big
return 4;
}
}
else if(val2>comp2){
// replace small
pr.first=pr.second; pr.second=id;
if(id>=9972&&id<=9985){
// sending small
return 4;
}
else{
// sending big
return 2+btbig[id-9986];
}
}
else{
// not replace
if(id>=9972&&id<=9985){
// sending small
return btsmol[id-9972];
}
else{
// sending big
return btbig[id-9986];
}
}
}
else if(pr.first==orib&&pr.second>=9972){
if(val1>comp1){
// replace big
pr.second=id;
if(id>=9972&&id<=9985){
// sending small
return 4;
}
else{
// sending big
return 2+btbig[id-9986];
}
}
else if(val2>comp2){
// replace small
pr.first=pr.second; pr.second=id;
if(id>=9972&&id<=9985){
// sending small
return 2;
}
else{
// sending big
return 4;
}
}
else{
// not replace
if(id>=9972&&id<=9985){
// sending small
return 0;
}
else{
// sending big
return btbig[id-9986];
}
}
}
}
std::pair<int, int> longest_path(std::vector<int> S) {
int smol=0,lar=0;
pr.first=-2; pr.second=-1;
for(int id=9972;id<=9999;id++){
if(pr.first>=9972&&pr.second>=9972){
if(S[i]==2){
// replace big
pr.second=id;
}
else if(S[i]==1){
// replace small
pr.first=pr.second; pr.second=id;
}
else{
// not replace
}
}
else if(pr.first==-2){
// replace big
if(id>=9972&&id<=9985){
// sending small
if(S[i]>=2&&S[i]<=3){
pr.second=id; smol+=(S[i]-2)*(1LL<<(id-9972));
}
else if(S[i]==4){
pr.first=pr.second; pr.second=id;
}
else{
smol+=(S[i])*(1LL<<(id-9972));
}
}
else{
// sending big
if(S[i]>=2&&S[i]<=3){
pr.first=pr.second; pr.second=id;
pr.second=id; lar+=(S[i]-2)*(1LL<<(id-9986));
}
else if(S[i]==4){
pr.second=id;
}
else{
lar+=(S[i])*(1LL<<(id-9986));
}
}
}
else if(pr.first==-1&&pr.second>=9972){
// replace big
pr.second=id;
if(id>=9972&&id<=9985){
// sending small
if(S[i]==4)pr.second=id;
else if(S[i]==2)pr.first=pr.second; pr.second=id;
else{}
}
else{
// sending big
if(S[i]>=2&&S[i]<=3){
pr.second=id;
lar+=(S[i]-2)*(1LL<<(id-9986));
}
else if(S[i]==4){
pr.first=pr.second; pr.second=id;
}
else{
lar+=(S[i])*(1LL<<(id-9986));
}
}
}
}
if(pr.first==-2)pr.first=smol;
if(pr.first==-1)pr.first=lar;
if(pr.second==-1)pr.second=lar;
return {pr.first,pr.second};
}