Submission #1284756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284756		janson0109	이주 (IOI25_migrations)	C++20	58 / 100	50 ms	1708 KiB

migrations

#include "migrations.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

int k = 27;
vector<vector<ll>> e;
pair<ll,pair<ll,ll>> diam;
ll ind = 0;

void dfs(ll root, ll d, vector<vector<ll>> &e, vector<bool> &vis, vector<ll> &dis) {
    vis[root] = 1, dis[root] = d;
    for(auto & v : e[root]) if(!vis[v]) dfs(v, d+1, e, vis, dis);
}
pair<ll,ll> findf(ll root, ll n, vector<vector<ll>> &e) {
    vector<bool> vis(n,0); vector<ll> dis(n,-1);
    dfs(root, 0, e, vis, dis);
    pair<ll,ll> ans = {-1,-1};
    for(ll i=0; i<n; i++) ans = max(ans, make_pair(dis[i], i));
    return ans;
}

int send_message(int N, int i, int Pi) {
    if(i == 1) e.push_back(vector<ll>());
    e.push_back(vector<ll>());
    e.back().push_back(Pi);
    e[Pi].push_back(i);
    if(i == N-k) {
        ll v = findf(0, i+1, e).S;
        pair<ll,ll> p = findf(v, i+1, e);
        diam.F = p.F, diam.S.F = v, diam.S.S = p.S;
        ind = diam.S.F*N + diam.S.S;
    }
    ll res =(ind & (1 << (i - (N-k)))) ? 1 : 0;
    if(i > N-k) {
        pair<ll,ll> p1 = findf(diam.S.F, i+1, e);
        pair<ll,ll> p2 = findf(diam.S.S, i+1, e);
        if(p1.F > diam.F) {
            diam.F = p1.F, diam.S.S = i;
            res += 2;
        }
        else if(p2.F > diam.F) {
            diam.F = p2.F, diam.S.F = i;
            res += 4;
        }
    }
    return res;
}

std::pair<int, int> longest_path(std::vector<int> S) {
    int N = 10000;
    ll ind = 0;
    for(int i=N-k; i<N; i++) ind += ((S[i] % 2) << (i - (N-k)));
    pair<int, int> ans = make_pair(ind / N, ind % N);
    for(int i=N-k; i<N; i++) {
        if(S[i] / 2 == 1) ans.S = i;
        if(S[i] / 2 == 2) ans.F = i;
    }
    return ans;
}

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