oj.uz

Submission #750867

# Submission time Handle Problem Language Result Execution time Memory
750867 2023-05-30T11:57:22 Z josanneo22 Cyberland (APIO23_cyberland) C++17
100 / 100
 388 ms 120960 KB 
#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;
template <typename T>
T inverse(T a, T m) {
	T u = 0, v = 1;
	while (a != 0) {
		T t = m / a;
		m -= t * a; swap(a, m);
		u -= t * v; swap(u, v);
	}
	assert(m == 1);
	return u;
}
 
template <typename T>
class Modular {
public:
	using Type = typename decay<decltype(T::value)>::type;
 
	constexpr Modular() : value() {}
	template <typename U>
	Modular(const U& x) {
		value = normalize(x);
	}
 
	template <typename U>
	static Type normalize(const U& x) {
		Type v;
		if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
		else v = static_cast<Type>(x % mod());
		if (v < 0) v += mod();
		return v;
	}
 
	const Type& operator()() const { return value; }
	template <typename U>
	explicit operator U() const { return static_cast<U>(value); }
	constexpr static Type mod() { return T::value; }
 
	Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
	Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
	template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
	template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
	Modular& operator++() { return *this += 1; }
	Modular& operator--() { return *this -= 1; }
	Modular operator++(int) { Modular result(*this); *this += 1; return result; }
	Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
	Modular operator-() const { return Modular(-value); }
 
	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
		value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
		return *this;
	}
	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
		int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
		value = normalize(value * rhs.value - q * mod());
		return *this;
	}
	template <typename U = T>
	typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
		value = normalize(value * rhs.value);
		return *this;
	}
 
	Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
 
	template <typename U>
	friend const Modular<U>& abs(const Modular<U>& v) { return v; }
 
	template <typename U>
	friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
	template <typename U>
	friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
	template <typename U>
	friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
 
private:
	Type value;
};
 
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
	assert(b >= 0);
	Modular<T> x = a, res = 1;
	U p = b;
	while (p > 0) {
		if (p & 1) res *= x;
		x *= x;
		p >>= 1;
	}
	return res;
}
 
template <typename T>
bool IsZero(const Modular<T>& number) {
	return number() == 0;
}
 
template <typename T>
string to_string(const Modular<T>& number) {
	return to_string(number());
}
 
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
	return stream << number();
}
 
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
	typename common_type<typename Modular<T>::Type, int64_t>::type x;
	stream >> x;
	number.value = Modular<T>::normalize(x);
	return stream;
}
 
/*
using ModType = int;
 
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/
 
constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
 
Mint C(int n, int k) {
	if (k < 0 || k > n) {
		return 0;
	}
	while ((int)fact.size() < n + 1) {
		fact.push_back(fact.back() * (int)fact.size());
		inv_fact.push_back(1 / fact.back());
	}
	return fact[n] * inv_fact[k] * inv_fact[n - k];
}
#define mp make_pair
#define pb push_back
#define fi first
#define se second 
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define out(x) cout<<x<<'\n'
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;
#define pii pair<int,int>
 
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int dx8[8] = { 0,0,-1,1,-1,1,-1,1 };
int dy8[8] = { -1,1,0,0,-1,1,1,-1 };
 
#include "cyberland.h"
 
struct dsu{
	vector<int> par,sz;
	int total_groups;
	void init(int n){
		par.resize(n); sz.resize(n);
		for(int i=0;i<n;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		if(par[x]==x) return x;
		else return par[x]=find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (sz[x] < sz[y]) swap(x, y);
		par[y] = x;
		sz[x] += sz[y];
		total_groups--;
	}
	bool same(int x,int y){
		x = find(x);
		y = find(y);
		if(x==y) return true;
		else return false;
	}
};
#define ld long double
double solve(int N, int M, int K, int H, vi fir, vi sec, vi co, vi arr) {
  K=min(K,69);
	vector<vpii> g(N);
	dsu ds; ds.init(N);
	for(int i=0;i<M;i++){
		if(fir[i]!=H && sec[i]!=H) ds.unite(fir[i],sec[i]);
		g[fir[i]].pb(mp(co[i],sec[i]));
		g[sec[i]].pb(mp(co[i],fir[i]));
	}
	vector<ld> pwr(K+1,1);
	for(int i=1;i<=K;i++){
		pwr[i]=pwr[i-1]/2;
	}
	arr[0]=0;
	vector<vector<ld>> dist(K+1,vector<ld>(N,1e18));
	using node=tuple<ld,int,int>;
	priority_queue<node,vector<node>,greater<node>> pq;
	auto enq=[&](int k,int x,ld d){
		if(dist[k][x]>d){
			dist[k][x]=d;
			pq.push({d,k,x});
		}
	};
	enq(K,H,0);
	while(pq.size()){
		auto [d,k,x]=pq.top(); pq.pop();
		if (dist[k][x] < d) continue;
		if (arr[x] == 0) return (double)d;
		for(auto&[c,v]:g[x]){
			if(ds.find(v)!=ds.find(0)) continue;
			enq(k,v,d+c*pwr[K-k]);
			if(arr[x]==2 && k>0) enq(k-1,v,d+c*pwr[K-k+1]);
		}
	}
	return (double)-1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 468 KB Correct.
2 Correct 30 ms 452 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1044 KB Correct.
2 Correct 28 ms 1128 KB Correct.
3 Correct 27 ms 1092 KB Correct.
4 Correct 28 ms 1080 KB Correct.
5 Correct 29 ms 992 KB Correct.
6 Correct 25 ms 6232 KB Correct.
7 Correct 32 ms 6096 KB Correct.
8 Correct 14 ms 12116 KB Correct.
9 Correct 26 ms 600 KB Correct.
10 Correct 26 ms 568 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 908 KB Correct.
2 Correct 29 ms 956 KB Correct.
3 Correct 27 ms 976 KB Correct.
4 Correct 25 ms 608 KB Correct.
5 Correct 25 ms 608 KB Correct.
6 Correct 6 ms 5076 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 34956 KB Correct.
2 Correct 27 ms 928 KB Correct.
3 Correct 24 ms 1032 KB Correct.
4 Correct 26 ms 932 KB Correct.
5 Correct 28 ms 608 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 928 KB Correct.
2 Correct 31 ms 972 KB Correct.
3 Correct 31 ms 936 KB Correct.
4 Correct 29 ms 6036 KB Correct.
5 Correct 36 ms 596 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 980 KB Correct.
2 Correct 24 ms 904 KB Correct.
3 Correct 60 ms 45796 KB Correct.
4 Correct 19 ms 3988 KB Correct.
5 Correct 27 ms 600 KB Correct.
6 Correct 25 ms 924 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 952 KB Correct.
2 Correct 4 ms 1236 KB Correct.
3 Correct 56 ms 37908 KB Correct.
4 Correct 49 ms 10136 KB Correct.
5 Correct 44 ms 23756 KB Correct.
6 Correct 31 ms 9684 KB Correct.
7 Correct 52 ms 10040 KB Correct.
8 Correct 50 ms 2100 KB Correct.
9 Correct 28 ms 1052 KB Correct.
10 Correct 25 ms 912 KB Correct.
11 Correct 51 ms 956 KB Correct.
12 Correct 29 ms 944 KB Correct.
13 Correct 28 ms 976 KB Correct.
14 Correct 49 ms 10668 KB Correct.
15 Correct 51 ms 3636 KB Correct.
16 Correct 29 ms 928 KB Correct.
17 Correct 31 ms 1092 KB Correct.
18 Correct 28 ms 932 KB Correct.
19 Correct 56 ms 908 KB Correct.
20 Correct 3 ms 468 KB Correct.
21 Correct 3 ms 876 KB Correct.
22 Correct 3 ms 1108 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1524 KB Correct.
2 Correct 5 ms 2248 KB Correct.
3 Correct 117 ms 120960 KB Correct.
4 Correct 50 ms 4900 KB Correct.
5 Correct 51 ms 45532 KB Correct.
6 Correct 32 ms 16208 KB Correct.
7 Correct 59 ms 22484 KB Correct.
8 Correct 58 ms 2136 KB Correct.
9 Correct 37 ms 1752 KB Correct.
10 Correct 35 ms 1584 KB Correct.
11 Correct 388 ms 608 KB Correct.
12 Correct 38 ms 1556 KB Correct.
13 Correct 37 ms 1528 KB Correct.
14 Correct 69 ms 47684 KB Correct.
15 Correct 73 ms 60052 KB Correct.
16 Correct 60 ms 20464 KB Correct.
17 Correct 55 ms 4684 KB Correct.
18 Correct 40 ms 1600 KB Correct.
19 Correct 39 ms 1564 KB Correct.
20 Correct 38 ms 1664 KB Correct.
21 Correct 74 ms 1568 KB Correct.
22 Correct 4 ms 588 KB Correct.
23 Correct 4 ms 1436 KB Correct.
24 Correct 4 ms 1620 KB Correct.