Submission #1267745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267745		nerrrmin	Migrations (IOI25_migrations)	C++20	30 / 100	814 ms	1424 KiB

migrations

#include "migrations.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e4 + 10;
int n;
vector < int > g[maxn];
int depth[maxn], recent, mx, best, still;
void dfs(int beg, int from, int dist)
{
    depth[beg] = dist;
    if(mx < depth[beg])
    {
        mx = dist;
        best = beg;
    }
    for (auto nb: g[beg])
    {
        if(nb == from)continue;
        dfs(nb, beg, dist+1);

    }
}
int bit = 0;
int send_message(int N, int i, int Pi)
{
    n = N;
    g[Pi].pb(i);
    g[i].pb(Pi);
    dfs(0, -1, 0);
    if(i == n-20)
    {
        recent = best;
        still = 1;
       int is = min(1, ((1 << bit) & recent));
       bit ++;
       return is;
    }
    else if(i > n-20)
    {
        if(best != recent && best == i)
        {
            still = 0;
            return 2;
        }
        else if(!still)return 0;
        else
        {
             int is = min(1, ((1 << bit) & recent));
             bit ++;
        return is;
        }

    }
    else return 0;
}

std::pair<int, int> longest_path(std::vector<int> S)
{
    n = S.size();
    std::pair < int, int > p;
    int last = 0;
    for (int i = n-20; i < n; ++ i)
    {
        if(S[i] == 2)
            last = i;

    }
    if(last == 0)
    {
        int b = 0;
        for (int i = n-20; i < n; ++ i)
        {
            last += ((1 << b)) * S[i];
            b ++;
        }

    }
    return make_pair(0, last);

}

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