제출 #1272691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272691		ihateojuz	World Map (IOI25_worldmap)	C++20	86 / 100	41 ms	5456 KiB

worldmap

#define _CRT_SECURE_NO_WARNINGS

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("O3")

//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Donald Trump pleese save this code
//Babahnineeleven will win IOI 2040
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Pavlyk is best coder in Khmelnytski

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstring> // �л� memset

using namespace std;

#define endl '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ll, ull> piu;
typedef std::pair <ld, ld> pdd;

const ll DIM = 100007;
const ld PI = 3.14159265358979;
const ll SQDIM = 460;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ll Bits = 32;
const ll Bsize = 300;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

FILE* stream;

void dfs(int val, int prev, vector < vector < int > >& v, vector < bool >& used, vector < int >& dfsOrder) {
	used[val] = true;
	for (auto to : v[val]) {
		if (to == prev || used[to]) continue;

		dfsOrder.push_back(to);
		dfs(to, val, v, used, dfsOrder);
		dfsOrder.push_back(val);
	}
}

vector < vector < int > > create_map(int N, int M, vector < int > A, vector < int > B) {
	vector < vector < int > > v(N + 1);
	for (int i = 0; i < M; i++) {
		v[A[i]].push_back(B[i]);
		v[B[i]].push_back(A[i]);
	}

	vector < int > dfsOrder;
	vector < bool > used(N + 1, false);

	dfsOrder.push_back(1);
	dfs(1, 1, v, used, dfsOrder);

	for (int i = 1; i <= N; i++) used[i] = false;

	vector < vector < int > > res(2 * N);
	int sh = 0;

	for (int d = 0; d < dfsOrder.size(); d++) {
		int ver = dfsOrder[d];

		if (d != 0) {
			for (int i = 0; i < 2 * N; i++) {
				res[i].push_back(ver);
			}
		}

		if (!used[ver]) {
			for (int i = 0; i < 2 * N; i++) {
				if (i % 2 == sh) {
					if ((i / 2) < v[ver].size()) res[i].push_back(v[ver][i / 2]);
					else res[i].push_back(ver);
					res[i].push_back(ver);
				}
				else if (d == 0) {
					res[i].push_back(ver);
				}
			}

			sh ^= 1;
			used[ver] = true;
		}
	}
	

	int mxH = 0;
	for (int i = 0; i < 2 * N; i++) mxH = max(mxH, (int)res[i].size());
	for (int i = 0; i < 2 * N; i++) {
		while (res[i].size() < mxH) res[i].push_back(res[i].back());
	}

	while (res.size() < mxH) res.push_back(res.back());
	
	return res;
}

/*
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
	//freopen_s(&stream, "input.txt", "r", stdin);
	//freopen_s(&stream, "output.txt", "w", stdout);
#endif

	//vector < vector < int > > res = create_map(5, 6, { 1, 2, 2, 1, 1, 2 }, { 2, 3, 4, 5, 5, 5 });
	vector < vector < int > > res = create_map(3, 2, {1, 2}, {2, 3});

	
	for (int i = 0; i < res.size(); i++) {
		for (int j = 0; j < res.size(); j++) {
			cout << res[i][j] << " ";
		}
		cout << endl;
	}

	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: 42 / 56