Submission #1256931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256931		Tymond	World Map (IOI25_worldmap)	C++20	86 / 100	52 ms	5448 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

vector<vi> g;
vi dep, parent;
int n;

void dfs(int v, int p, int d){
    dep[v] = d;
    parent[v] = p;
    for(auto u : g[v]){
        if(u == 0 || dep[u] != 0){
            continue;
        }
        dfs(u, v, d + 1);
    }
} 

vector<vi> f(int v){
    vector<vi> vec;
    int mx = 0;
    for(auto u : g[v]){
        if(dep[u] == dep[v] + 1){
            vec.pb(vi());
            vec.back().assign(1, v);
            vector<vi> curr = f(u);
            for(auto ele : curr){
                vec.pb(ele);
            }
            mx = max(mx, sz(curr.back()));
        }
    }

    vec.pb(vi());
    vec.back().assign(1, v);
    for(int i = 0; i < sz(vec); i++){
        while(sz(vec[i]) < mx + 1){
            vec[i].pb(v);
        }
    }

    int wsk = 1;
    for(auto u : g[v]){
        if(dep[u] > dep[v] + 1){
            vec[wsk].pb(u);
            wsk += 2;
        }
    }

    for(int i = 0; i < sz(vec); i++){
        while(sz(vec[i]) < mx + 3){
            vec[i].pb(v);
        }
    }
    return vec;
}

vector<vi> create_map(int N, int M, vi A, vi B){
    g.assign(N, vi());
    parent.assign(N, 0);
    dep.assign(N, 0);
    n = N;
    for(int i = 0; i < M; i++){
        A[i]--;
        B[i]--;
        g[A[i]].pb(B[i]);
        g[B[i]].pb(A[i]);
    }

    dfs(0, 0, 0);

    vector<vi> map = f(0);
    for(int i = 0; i < sz(map); i++){
        for(int j = 0; j < sz(map[i]); j++){
            map[i][j]++;
        }
    }
    while(sz(map) < 3 * n){
        map.pb(vi(3 * n, 1));
    }
    for(int i = 0; i < sz(map); i++){
        while(sz(map[i]) < 3 * n){
            map[i].pb(1);
        }
    }
    return map;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 42 / 56