Submission #1284778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284778		Luvidi	이주 (IOI25_migrations)	C++20	0 / 100	490 ms	1108 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 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-4-2-1,12,4,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=x2*a[t-1]+y2;
            // cout<<x<<' '<<y<<' '<<x2<<' '<<y2<<' '<<ms<<'\n';
        }
        s+=a[t];
    }
    if(i>=n-a[0]){
        int t=ms%5;
        ms/=5;
        return t;
    }
    return 0;
}

std::pair<int, int> longest_path(std::vector<int> m) {
    int n=m.size();
    int a[]={n-12-4-2-1,12,4,2,1},x=0,y=0;
    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];
        int x2=d[t]/a[t-1],y2=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: 0 / 30
• Subtask 2: 0 / 70