Submission #1258208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258208		stapanulocu1	World Map (IOI25_worldmap)	C++20	72 / 100	99 ms	9800 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;

const int NR = 42;

vector<int> v[NR];
bool done[NR];
int n, m, res[NR * 10][NR * 10], lines;

void fill(int node)
{
    int nr = 0;
    for (int i = 0; i < v[node].size(); ++i)
    {
        res[lines][nr] = v[node][i];
        res[lines][nr + 1] = node;
        nr += 2;
    }
    for (int i = nr; i < NR * 10; ++i)
        res[lines][i] = node;
    ++lines;

    for (int i = 0; i < NR * 10; ++i)
        res[lines][i] = node;
    ++lines;
}

void solve(int node)
{
    done[node] = 1;

    for (int i = 0; i < NR * 10; ++i)
        res[lines][i] = node;
    ++lines;

    bool did;

    fill(node);

    did = false;

    for (int i = 0; i < v[node].size(); ++i)
    {
        if (!done[v[node][i]])
        {
            did = true;
            solve(v[node][i]);

            for (int j = 0; j < NR * 10; ++j)
                res[lines][j] = node;
            ++lines;
        }
    }

    if (!did)
        return;

    for (int i = 0; i < NR * 10; ++i)
        res[lines][i] = node;
    ++lines;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B)
{
    n = N;
    m = M;

    for (int i = 0; i <= n; ++i)
    {
        v[i].clear();
        done[i] = 0;
    }
    lines = 0;

    for (int i = 0; i < m; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    solve(1);

    for (int i = 0; i < lines; ++i)
    {
        if (res[i][0] == res[i + 1][0])
        {
            for (int j = i; j < lines; ++j)
            {
                for (int k = 0; k < NR * 10; ++k)
                    res[j][k] = res[j + 1][k];
            }
            --i;
            --lines;
        }
    }

    vector<vector<int>> re;
    int laste = res[lines - 1][0];
    for (int i = lines; i < 2 * n; ++i)
    {
        for (int j = 0; j < 10 * NR; ++j)
        {
            res[i][j] = laste;
        }
    }
    for (int i = 0; i < max(lines, 2 * n); ++i)
    {
        vector<int> a;
        re.push_back(a);
        for (int j = 0; j < max(lines, 2 * n); ++j)
        {
            re[i].push_back(res[i][j]);
        }
    }
    if (lines > 240)
        while (1)
            ;
    return re;
}
/*
int main()
{
    vector<vector<int>> re;
    vector<int> a = {1, 1, 2, 3}, b = {2, 3, 4, 4};
    re = create_map(4, a.size(), a, b);
    for (int i = 0; i < re.size(); ++i)
    {
        for (int j = 0; j < re[i].size(); ++j)
        {
            cerr << re[i][j] << " ";
        }
        cerr << "\n";
    }
    return 0;
}*/

• 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