Submission #1270821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270821		nerrrmin	World Map (IOI25_worldmap)	C++20	0 / 100	10 ms	580 KiB

worldmap

#include "worldmap.h"
#define pb push_back

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;

int n, m;
vector < pair < int, int > > g[maxn];
int tmr, a[maxn];
int seen[maxn], label[maxn], is_label[maxn];
int noneed[maxn];
void dfs(int beg, int from)
{
    seen[beg] = 1;
    tmr ++;
    a[tmr] = beg;
    label[beg] = tmr;
    is_label[tmr] = 1;
    for (auto &[nb, i]: g[beg])
    {
        if(nb == from)
            continue;
        if(seen[nb] == 1)continue;
        noneed[i] = 1;
        dfs(nb, beg);
        tmr ++;
        a[tmr] = beg;
    }
}
unordered_map < int, int > mp;
int diff[maxn * 4], sz[maxn * 4];
int diag[maxn * 4];

int type[maxn * 4], col[maxn * 4], space[maxn * 4];

bool cmp(int col1, int col2)
{
    if(space[col1] < space[col2])return true;
    return false;
}
int used[maxn];
vector < int > take[maxn];
vector < pair <int, int > > cells[maxn * 4];
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{

    n = N;
    m = M;
    mp.clear();
    for (int i = 0; i <= n; ++ i)
    {
        g[i].clear();
        take[i].clear();
        used[i] = 0;
        seen[i] = 0;
    }
    for (int i = 1; i <= 15*n; ++ i)
    {
        cells[i].clear();
        diff[i] = 0;
        sz[i] = 0;
        diag[i] = 0;
        type[i] = 0;
        sz[i] = 0;
        space[i] = 0;
        col[i] = 0;
    }
    for (int i = 0; i < m; ++ i)
    {
        noneed[i] = 0;
        int from = A[i], to = B[i];
        g[from].pb(make_pair(to, i));
        g[to].pb(make_pair(from, i));
    }
    tmr = 0;
    for (int i = 1; i <= tmr; ++ i)
    {
        seen[i] = 0;
        is_label[i] = 0;
        a[i] = 0;
        label[i] = 0;
    }
    dfs(1, -1);
    int r = 0;
    int currsz = 1;
    for (int i = -2*n+1; i < 2*n; ++ i)
    {
        r ++;
        diff[r] = i;
        mp[i] = r;

        sz[r] = currsz;
        if(i < 0)
            currsz ++;
        else
            currsz --;
    }
    int on = 0;


   // cout << " !! " << endl;
    for (int i = 1; i <= tmr; ++ i)
    {
        //cout << a[i] << " ,, ";
        on ++;
        type[on] = 1;
        col[on] = a[i];
        if(is_label[i] == 1)
        {
            on ++;
            type[on] = 2;
            col[on] = a[i];
            space[a[i]] = sz[on];
            on ++;
            type[on] = 1;
            col[on] = a[i];

        }
    }
    assert(on <= r);
   // cout << endl;
    vector < int > u;
    for (int i = 1; i <= n; ++ i)
        u.pb(i);
    sort(u.begin(), u.end(), cmp);
    for (auto x: u)
    {
        used[x] = 1;
        for (auto &[nb, i]: g[x])
        {
            if(noneed[i])continue;
            if(used[nb])take[x].pb(nb);
        }
        take[x].pb(x);
    }

    for (int i = 0; i < 2*n; ++ i)
    {
        for (int j = 0; j < 2*n; ++ j)
        {
            int diff = i - j;
            int diag = mp[diff];
            cells[diag].pb(make_pair(i, j));
        }
    }

    std::vector<std::vector<int>> ans(2 * n, std::vector<int>(2*n, 1));
    int last = 0;
    assert(r <= 4*n);
    for (int i = 1; i <= r; ++ i)
    {
        int cvqt = col[i];
        if(cvqt == 0)cvqt = last;
        if(type[i] != 2)
        {
            for (auto x: cells[i])
                ans[x.first][x.second] = cvqt;
        }
        else
        {
            int j = 0;
            for(auto x: cells[i])
            {
                ans[x.first][x.second] = take[cvqt][j];
                if(j < (int)(take[cvqt].size()-1))j ++;
            }
          //  assert(j > take[cvqt].size() - 2);
        }
        last = cvqt;
    }

    return ans;
}

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