oj.uz

Submission #736439

# Submission time Handle Problem Language Result Execution time Memory
736439 2023-05-05T16:15:07 Z vjudge1 Birmingham (COCI20_birmingham) C++17
70 / 70
 116 ms 11304 KB 
// No bits/stdc++.h because clang

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <cassert>
#include <random>
#include <type_traits>
#include <list>
#include <tuple>
#include <climits>

// I don't know how any of these work, but its nice to have them
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline,unsafe-math-optimizations")
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template <typename T>
void debug(T &x, std::string name = "")
{
	if (name == "")
		std::cerr << ":= " << x << "\n";
	else
		std::cerr << name << " = " << x << "\n";
}
template <typename T>
void debugArr(T &arr, int n = -1, std::string name = "")
{
	if (n == -1)
		n = sizeof(arr) / sizeof(arr[0]);
	if (name == "")
		std::cerr << ":= ";
	else
		std::cerr << name << " = ";
	std::cerr << "[";
	for (int i = 0; i < n; i++)
		std::cerr << arr[i] << ","[i == n - 1];
	std::cerr << "]"
			  << "\n";
}
template <typename T>
void debugArr(std::vector<T> &arr, int n = -1, std::string name = "")
{
	if (n == -1)
		n = arr.size();
	if (name == "")
		std::cerr << ":= ";
	else
		std::cerr << name << " = ";
	std::cerr << "[";
	for (int i = 0; i < n; i++)
		std::cerr << arr[i] << ","[i == n - 1];
	std::cerr << "]"
			  << "\n";
}
using namespace std;
/******************* Uncomment this for long long (TLE) *******************/
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define mint map<int, int>
#define sint set<int>
#define msint multiset<int>
#define qint queue<int>
#define pqint priority_queue<int>
#define lint list<int>
#define stint stack<int>
#define gint greater<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define guv   \
	int u, v; \
	cin >> u >> v
#define sz(x) (int)x.size()
#define cinarr(x, n)            \
	for (int i = 0; i < n; i++) \
	cin >> x[i]
#define coutarr(x, n)           \
	for (int i = 0; i < n; i++) \
		cout << x[i] << " ";    \
	cout << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define _reset(x, y) memset(x, y, sizeof(x))
#define _mid ((l + r) >> 1)
#define endl "\n"
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FILEIO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)

inline void swap(int &a, int &b)
{
	a ^= b;
	b ^= a;
	a ^= b;
}

inline int gcd(int a, int b)
{
	while (b)
	{
		a %= b;
		swap(a, b);
	}
	return a;
}

/*
 _____ ____  ____  ____    _     _     ____  _  __
/  __//  _ \/  _ \/  _ \  / \   / \ /\/   _\/ |/ /
| |  _| / \|| / \|| | \|  | |   | | |||  /  |   /
| |_//| \_/|| \_/|| |_/|  | |_/\| \_/||  \_ |   \
\____\____/\____/\____/  \____/\____/\____/\_|\_\
*/
vint g[100005];
#define INF 1000000000
inline void solve()
{

	int n, m, q, k;
	cin >> n >> m >> q >> k;
	queue<int> qu;
	vector<int> dist(n + 1, INF);
	for (int i = 0; i < q; ++i)
	{
		int x;
		cin >> x;
		qu.push(x);
		dist[x] = 0;
	}
	for (int i = 0; i < m; ++i)
	{
		guv;
		g[u].pb(v);
		g[v].pb(u);
	}

	while (!qu.empty())
	{
		int u = qu.front();
		qu.pop();
		for (auto v : g[u])
		{
			if (dist[v] > dist[u] + 1)
			{
				dist[v] = dist[u] + 1;
				qu.push(v);
			}
		}
	}
	vint s;
	s.pb(0);
	s.pb(k);
	for (int i = 2; i * k <= n + 5; ++i)
	{
		s.pb(i * k + s.back());
	}
	/* for (auto i : s)
		cout << i << " ";
	cout << endl;
	cout << dist[3] << endl; */
	for (int i = 1; i <= n; ++i)
	{
		// index of upper bound
		int idx = lower_bound(all(s), dist[i]) - s.begin();
		cout << idx << " ";
	}

	// My code is not working!!! Try these fixes:
	// 1. Check for overflow (uncommenct #define int long long)
	// 2. Check for array bounds
	// 3. Check for array indexes, 1-indexed or 0-indexed?
	// 4. Check for special cases (n=1?)
	// 5. Check for multiple test cases (remember to clear global variables)
	// 6. Check the limits of your data types maybe l <= r, maybe 0 <= n...

	// Getting TLE? Try these fixes:
	// 1. Delete the line: #define int long long
	// 2. Use array instead of vector

	// Getting WA? Good luck, you're on your own
}

signed main()
{
	int t = 1;
	FASTIO;
	/******************* Uncomment this if you want to read from input.txt ********************/


	/***************** Uncomment this if you want to test multiple test cases *****************/
	// cin >> t;

	for (int i = 1; i <= t; i++)
	{
		/**************** Uncomment this if you want to print the case number ****************/
		// cout << "Case " << i << ":" << endl;
		solve();
	}

	return '0' ^ '0';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9848 KB Output is correct
2 Correct 110 ms 11068 KB Output is correct
3 Correct 107 ms 11204 KB Output is correct
4 Correct 90 ms 9220 KB Output is correct
5 Correct 83 ms 9452 KB Output is correct
6 Correct 106 ms 10224 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 10320 KB Output is correct
2 Correct 94 ms 10840 KB Output is correct
3 Correct 103 ms 10960 KB Output is correct
4 Correct 106 ms 10572 KB Output is correct
5 Correct 82 ms 10044 KB Output is correct
6 Correct 84 ms 9560 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10056 KB Output is correct
2 Correct 96 ms 11304 KB Output is correct
3 Correct 109 ms 11212 KB Output is correct
4 Correct 84 ms 10504 KB Output is correct
5 Correct 65 ms 9584 KB Output is correct
6 Correct 69 ms 9720 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9544 KB Output is correct
2 Correct 90 ms 10820 KB Output is correct
3 Correct 83 ms 11136 KB Output is correct
4 Correct 77 ms 9872 KB Output is correct
5 Correct 73 ms 9320 KB Output is correct
6 Correct 96 ms 9904 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9420 KB Output is correct
2 Correct 70 ms 10600 KB Output is correct
3 Correct 71 ms 10436 KB Output is correct
4 Correct 87 ms 10068 KB Output is correct
5 Correct 78 ms 9680 KB Output is correct
6 Correct 67 ms 9724 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9560 KB Output is correct
2 Correct 70 ms 10600 KB Output is correct
3 Correct 76 ms 10312 KB Output is correct
4 Correct 90 ms 10096 KB Output is correct
5 Correct 76 ms 9548 KB Output is correct
6 Correct 77 ms 9944 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9676 KB Output is correct
2 Correct 68 ms 10104 KB Output is correct
3 Correct 116 ms 11112 KB Output is correct
4 Correct 66 ms 9684 KB Output is correct
5 Correct 76 ms 9812 KB Output is correct
6 Correct 80 ms 10336 KB Output is correct