Submission #1311942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311942		Cyanberry	World Map (IOI25_worldmap)	C++20	86 / 100	37 ms	5644 KiB

worldmap

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

vector<int> visited;
vector<int> ret;
vector<vector<int>> graf, extras;
bool dfs(int curr, int depth) {
	if (visited[curr]) return false;
	visited[curr] = depth;
	for (int i = 0; i < graf[curr].size(); ++i) {
		ret.push_back(curr+1);
		if (visited[graf[curr][i]] > depth) {
			extras[curr].push_back(graf[curr][i]+1);
		}
		if (visited[graf[curr][i]]) continue;
		dfs(graf[curr][i], depth + 1);
	}
	ret.push_back(curr+1);
	return true;
}

std::vector<std::vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
	ret.clear();
	visited.assign(N, 0);
	graf.assign(N, vector<int>{});
	extras.assign(N, vector<int>{});
	for (int i = 0; i < M; ++i) {
		graf[A[i]-1].push_back(B[i] - 1);
		graf[B[i]-1].push_back(A[i] - 1);
	}
	// cout<<"E"<<endl;
	dfs(0, 1);
	// cout<<"S"<<ret.size()<<endl;
	vector<bool> exists(N+1, false);
	vector<int> doubleBars(ret.size() * 2, 0);
	vector<vector<int>> ans;
	int id = 1;
	int len = 0;
	for (int i = 0; i < ret.size(); ++i) {
		if (i > 0 && ret[i] == ret[i-1]) continue;
		if (exists[ret[i]]) {
			++len;
			continue;
		}
		exists[ret[i]] = true;
		doubleBars[len] = id;
		++id;
		len += 2;
	}
	exists.assign(N+1, false);
	for (int i = 0; i < ret.size(); ++i) {
		if (i > 0 && ret[i] == ret[i-1]) continue;
		if (exists[ret[i]]) {
			ans.push_back(vector<int>(len, ret[i]));
			continue;
		}
		exists[ret[i]] = true;
		for (int j = 0; j <= 1; ++j) {
			// cout<<(3 * i + j)<<endl;
			ans.push_back(vector<int>(len, ret[i]));
			if (j == 0) {
				for (int k = 0; k < extras[ret[i]-1].size(); ++k) {
					ans[ans.size()-1][2*k + (doubleBars[ans.size()-1] & 1)] = extras[ret[i]-1][k];
					for (int l = ans.size()-2; l >= 0; --l) {
						ans[l][2*k+(doubleBars[ans.size()-1] & 1)] = ans[l+1][2*k + (doubleBars[ans.size()-1] & 1)+1];
						if (doubleBars[l] != 0) {
							break;
						}
					} 
				}
			}
		}
	}
	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: 42 / 56