Submission #1284806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284806		Luvidi	이주 (IOI25_migrations)	C++20	30 / 100	830 ms	1392 KiB

migrations

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

const int maxn=1e4;
vector<int> ad[maxn];
int ms,x,y,mx=-1,cr;

void dfs(int v,int p,int d){
    if(d>mx){
        mx=d;
        x=v,y=cr;
    }
    for(int u:ad[v])if(u!=p)dfs(u,v,d+1);
}

int dc(int x,int y,int z){
    if(!x&&!y)return 0;
    int t=0;
    for(int i=0;i<x;i++)t+=z-i;
    return t+y-x;
}

pair<int,int> ec(int s,int z){
    int x=0;
    for(int i=0;s-(z-i)>0;i++){
        x++;
        s-=z-i;
    }
    return {x,x+s};
}

int send_message(int n, int i, int pi) {
    ad[i].push_back(pi);
    ad[pi].push_back(i);   
    cr=i;
    dfs(i,i,0);
    int a[]={n-12-3-2-1,12,3,2,1};
    for(int t=1,s=a[0];t<=4;t++){
        if(i==s){
            int x2=max(0,x-(s-a[t-1])),y2=max(0,y-(s-a[t-1]));
            ms=dc(x2,y2,a[t-1]);
            // cout<<x<<' '<<y<<' '<<x2<<' '<<y2<<' '<<ms<<'\n';
        }
        s+=a[t];
    }
    int t=ms%5;
    ms/=5;
    return t;
}

std::pair<int, int> longest_path(std::vector<int> m) {
    int n=m.size();
    int a[]={n-12-3-2-1,12,3,2,1},x=0,y=0;
    for(int i=1;i<=4;i++)assert(a[i-1]*(a[i-1]+1)/2+1<=pow(5,a[i]));
    int d[5];
    for(int t=1,s=a[0];t<=4;t++){
        d[t]=0;
        for(int i=s+a[t]-1;i>=s;i--)d[t]=5*d[t]+m[i];
        auto[x2,y2]=ec(d[t],a[t-1]);
        // cout<<x2<<' '<<y2<<' '<<d[t]<<'\n';
        if(x2)x=x2+(s-a[t-1]);
        if(y2)y=y2+(s-a[t-1]);
        s+=a[t];
    }
    return {x,y};
}

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