Submission #1250035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250035		Aliyyiakbar	World Map (IOI25_worldmap)	C++20	72 / 100	138 ms	9816 KiB

worldmap

#include "bits/stdc++.h"
#include "worldmap.h"
using namespace std;

const int sz = 1e6 + 9;

vector<vector<int>> ans;
vector<vector<int>> v;
bitset<sz> bs;

int r;

void color(int c)
{
    for (int i = 0; i < (int)ans[r].size(); ++i)
    {
        if (!ans[r][i])
        {
            ans[r][i] = c;
        }
    }
    ++r;
}

bool dfs(int node)
{
    if (bs[node] == 1)
    {
        return false;
    }
    bs[node] = 1;
    color(node);
    for (int i = 0; i < (int)v[node].size(); ++i)
    {
        ans[r][i << 1LL] = v[node][i];
    }
    color(node);
    color(node);
    for (auto to : v[node])
    {
        if (dfs(to))
        {
            color(node);
        }
    }
    return true;
}

vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b)
{
    ans.assign(n << 2LL, vector<int>(n << 2LL, 0LL));
    v.assign(n + 1, vector<int>());
    for (int i = 0; i <= 1e6; ++i)
    {
        bs[i] = 0;
    }
    for (int i = 0; i < m; ++i)
    {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    r = 0l;
    dfs(1);
    while(r < (int)ans.size())
    {
        color(ans[r - 1][0]);
    }
    return ans;
}

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