제출 #1302217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302217		Valaki2	World Map (IOI25_worldmap)	C++20	72 / 100	68 ms	9580 KiB

worldmap

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

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

int n, m;
vector<vector<pii > > graph;
vector<pii > edges;
vector<bool> done_edge;
vector<bool> vis;
vector<int> order;

const vector<pii > direction = {mp(-1, 0), mp(0, -1), mp(0, 1), mp(1, 0)};

void dfs(int cur) {
    vis[cur] = true;
    for(pii nei : graph[cur]) {
        if(!vis[nei.fi]) {
            order.pb(cur);
            dfs(nei.fi);
            done_edge[nei.se] = true;
        }
    }
    order.pb(cur);
}

void reset() {
    n = m = 0;
    graph.clear();
    edges.clear();
    done_edge.clear();
    vis.clear();
    order.clear();
}

vector<vector<int> > create_map(int N, int M, vector<int> A, vector<int> B) {
    reset();
    n = N, m = M;
    graph.resize(1 + n);
    edges.resize(m);
    done_edge.assign(m, false);
    for(int i = 0; i < m; i++) {
        graph[A[i]].pb(mp(B[i], i));
        graph[B[i]].pb(mp(A[i], i));
        edges[i] = mp(A[i], B[i]);
    }
    int root = 1;
    vis.assign(1 + n, false);
    order.pb(root);
    dfs(root);
    order.pb(root);
    vector<vector<int> > pre_ans(2 * n, vector<int> (2 * n, 0));
    for(int i = 1; i <= 2 * n; i++) {
        pre_ans[i - 1][0] = order[i - 1];
        pre_ans[i - 1][1] = order[i];
        for(int j = 2; j < 2 * n; j++) {
            pre_ans[i - 1][j] = order[i];
        }
    }
    vector<vector<int> > ans(4 * n, vector<int> (4 * n, 0));
    vector<queue<pii > > where_to(1 + n);
    for(int i = 0; i < 4 * n; i++) {
        for(int j = 0; j < 4 * n; j++) {
            ans[i][j] = pre_ans[i / 2][j / 2];
        }
    }
    for(int i = 0; i < 2 * n; i++) {
        for(int j = 2; j < 2 * n; j++) {
            where_to[pre_ans[i][j]].push(mp(2 * i, 2 * j + ((i % 2 == 1) ? 1 : 0)));
        }
    }
    for(int i = 0; i < m; i++) {
        if(!done_edge[i]) {
            pii pos = where_to[A[i]].front();
            where_to[A[i]].pop();
            ans[pos.fi][pos.se] = B[i];
            for(pii dir : direction) {
                pii cur_pos = mp(pos.fi + dir.fi, pos.se + dir.se);
                if(cur_pos.fi >= 0 && cur_pos.fi < 4 * n && cur_pos.se >= 0 && cur_pos.se < 4 * n) {
                    ans[cur_pos.fi][cur_pos.se] = A[i];
                }
            }
        }
    }
    return ans;
    /*vector<vector<int> > ans(2 * N, vector<int> (2 * N, 1));
    if (M > 0) {
        ans[0][0] = A[0];
        ans[0][1] = B[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