Submission #1307308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307308		MunkhErdene	World Map (IOI25_worldmap)	C++17	100 / 100	76 ms	3876 KiB

worldmap

#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const ll NAIM = 9e18;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    ll n = N, m = M;
    ll lo = 1, hi = 240;
    vector<vector<int>> res;
    ll sz = NAIM;
    while(lo <= hi) {
        vector<set<ll>> g(n + 1);
        vector<vector<ll>> g1(n + 1);
        FOR(i, 0, m) {
            ll u = A[i], v = B[i];
            g[u].insert(v);
            g[v].insert(u);
            g1[u].pb(v);
            g1[v].pb(u);
        }

        ll k = (lo + hi) / 2;
        vector<vector<int>> cur(k, vector<int> (k, 0));
        pair<ll, ll> last = {0, 0};
        auto ok = [&](ll x, ll y) {
            return 0 <= x && x < k && 0 <= y && y < k;
        };     
        ll last_country = 1;
        function<void(ll, ll, ll, ll, ll)> dfs = [&](ll country, ll x, ll y, ll now, ll state) {
            last_country = country;
            if(state == 0) cur[x][y] = country;
            else cur[x][y] = now;
            ll x1 = x + 1, y1 = y - 1;
            if(ok(x1, y1)){
                if(state == 1){
                    if(g[country].empty()) dfs(country, x1, y1, country, 1);
                    else {
                        auto it = g[country].begin();
                        ll to = *it;
                        g[country].erase(it);
                        g[to].erase(country);
                        dfs(country, x1, y1, to, 1);
                    }
                }
                else dfs(country, x1, y1, country, 0);
            }
            else{
                if(last.ss < k - 1) last.ss++;
                else last.ff++;
                if(ok(last.ff, last.ss) == false) return;
                if(state == 0) {
                    if(g[country].empty()) return;
                    else {
                        auto it = g[country].begin();
                        ll to = *it;
                        g[country].erase(it);
                        g[to].erase(country);
                        dfs(country, last.ff, last.ss, to, 1);
                    }
                }
                else dfs(country, last.ff, last.ss, country, 0);
            }
        };
        vector<ll> walk;
        vector<bool> vis(n + 1, 0);
        function<void(ll)> dfs1 = [&](ll u) {
            vis[u] = 1;
            walk.pb(u);
            for(auto &v : g1[u]) {
                if(!vis[v]) {
                    dfs1(v);
                    walk.pb(u);
                }
            }
        };
        FOR(i, 1, n + 1) {
            if(!vis[i]) {
                dfs1(i);
                break;
            }
        }
        for(auto &x : walk) {
            if(ok(last.ff, last.ss) == false) break;
            dfs(x, last.ff, last.ss, x, 0);
        }
        FOR(i, 0, k) {
            FOR(j, 0, k) {
                if(cur[i][j] == 0) {
                    cur[i][j] = last_country;
                }
            }
        }
        bool flag = 1;
        FOR(i, 1, n + 1) if(!g[i].empty()) flag = 0;
        if(flag) {
            hi = k - 1;
            if(k < sz) {
                sz = k;
                res = cur;
            }
        }
        else {
            lo = k + 1;
        }
    }
    return res;
}

• 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: 56 / 56