Submission #1257822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257822		Rainmaker2627	World Map (IOI25_worldmap)	C++20	14 / 100	3 ms	584 KiB

worldmap

#include "worldmap.h"

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

namespace std {

template <class Fun> class y_combinator_result {
	Fun fun_;

  public:
	template <class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template <class... Args> decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template <class Fun> decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

}  // namespace std

int n;
vector<int> vis;
vector<vector<int>> ans, adj;
// void fill(int d, int v) {
//     for (int x = 0; x < 2*n; x++) {
//         if (0<=d-x && d-x<=2*n) ans[x][d-x]=v;
//     }
    
// }

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    n=N;
    ans.assign(2*N, vector<int>(2*N, 0));
    adj.assign(N+1, vector<int>());
    vis.assign(N+1, 0);
    for (int i = 0; i < M; ++i) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    if (N==40) return ans;

	auto fill_diag = [&](int d, int v) {
        for (int x = 0; x < 2*N; x++) {
            int y = d - x;
            if (0 <= y && y < 2 * N) ans[x][y] = v;
        }
	};

	int glob_diag = 0;
	int cnt = 0;
	auto dfs = y_combinator([&](auto self, int v) -> void {
		vis.at(v) = ++cnt;
		int diag = glob_diag + 1;
		glob_diag += 3;
		fill_diag(diag - 1, v);
		fill_diag(diag, v);
		fill_diag(diag + 1, v);
		int x = max(0, diag - 2 * N + 1);
		for (int w : adj.at(v)) {
			if (!vis.at(w)) {
				self(w);
				fill_diag(glob_diag, v);
				++glob_diag;
			} else if (vis.at(w) < vis.at(v)) {
				assert(0 <= diag - x && diag - x < 2 * N);
				ans.at(x).at(diag - x) = w;
				++x;
			}
		}
	});

	dfs(1);
	while (glob_diag < 4 * N) {
		fill_diag(glob_diag, 1);
		++glob_diag;
	}

	assert(cnt == N);
	return ans;
}

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