Submission #1270689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270689		nerrrmin	세계 지도 (IOI25_worldmap)	C++20	0 / 100	10 ms	576 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 < int > g[maxn];
int tmr, a[maxn];
int seen[maxn], label[maxn], is_label[maxn];
void dfs(int beg, int from)
{
    seen[beg] = 1;
    cout << beg << " anddd from " << from << endl;
    tmr ++;
    a[tmr] = beg;
    label[beg] = tmr;
    is_label[tmr] = 1;
    for (auto nb: g[beg])
    {
        if(nb == from)
            continue;
        if(seen[nb] == 1)continue;
        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;
    for (int i = 0; i < m; ++ i)
    {
        int from = A[i], to = B[i];
        g[from].pb(to);
        g[to].pb(from);
    }

    for (int i = 1; i <= n; ++ i)
    {
        cout <<"sysedi na "  << i << endl;
        for (auto x: g[i])
            cout << x << " ";
        cout << endl;
    }
    dfs(1, -1);
    cout << "flag 1" << endl;
    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;


    for (int i = 1; i <= tmr; ++ i)
    {
        on ++;
        type[on] = 1;
        col[on] = a[i];
        if(is_label[i] == 1)
        {
            on ++;
            type[on] = 2;
            col[on] = a[i];
            on ++;
            type[on] = 1;
            col[on] = a[i];
            space[a[i]] = sz[on];
        }
    }

    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: g[x])
        {
            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));
    for (int i = 1; i <= r; ++ i)
    {
        int cvqt = col[i];

        if(type[i] == 1)
        {
            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 < take[cvqt].size()-1)j ++;
            }
        }
    }


    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