Submission #750845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
750845	2023-05-30T11:43:09 Z	josanneo22	Cyberland (APIO23_cyberland)	C++17	97 / 100	1240 ms	2097152 KB

cyberland

#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;
	}
};
double solve(int N, int M, int K, int H, vi fir, vi sec, vi co, vi arr) {
	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<double> pwr(K+1,1);
	for(int i=1;i<=K;i++){
		pwr[i]=pwr[i-1]/2;
	}
	arr[0]=0;
	vector<vector<double>> dist(K+1,vector<double>(N,1e18));
	using node=tuple<double,int,int>;
	priority_queue<node,vector<node>,greater<node>> pq;
	auto enq=[&](int k,int x,double 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 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 -1;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	456 KB	Correct.
2	Correct	28 ms	468 KB	Correct.

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	720 KB	Correct.
2	Correct	30 ms	700 KB	Correct.
3	Correct	24 ms	712 KB	Correct.
4	Correct	26 ms	700 KB	Correct.
5	Correct	25 ms	652 KB	Correct.
6	Correct	20 ms	3664 KB	Correct.
7	Correct	27 ms	3648 KB	Correct.
8	Correct	17 ms	7252 KB	Correct.
9	Correct	31 ms	496 KB	Correct.
10	Correct	25 ms	504 KB	Correct.

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	768 KB	Correct.
2	Correct	23 ms	700 KB	Correct.
3	Correct	22 ms	692 KB	Correct.
4	Correct	26 ms	484 KB	Correct.
5	Correct	35 ms	508 KB	Correct.
6	Correct	5 ms	3028 KB	Correct.

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	20288 KB	Correct.
2	Correct	23 ms	704 KB	Correct.
3	Correct	22 ms	776 KB	Correct.
4	Correct	22 ms	724 KB	Correct.
5	Correct	26 ms	500 KB	Correct.

Subtask #5

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	712 KB	Correct.
2	Correct	27 ms	712 KB	Correct.
3	Correct	25 ms	708 KB	Correct.
4	Correct	26 ms	3584 KB	Correct.
5	Correct	24 ms	488 KB	Correct.

Subtask #6

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	692 KB	Correct.
2	Correct	21 ms	728 KB	Correct.
3	Correct	63 ms	26868 KB	Correct.
4	Correct	18 ms	2352 KB	Correct.
5	Correct	26 ms	468 KB	Correct.
6	Correct	23 ms	732 KB	Correct.

Subtask #7

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	680 KB	Correct.
2	Correct	4 ms	852 KB	Correct.
3	Correct	50 ms	23876 KB	Correct.
4	Correct	45 ms	6260 KB	Correct.
5	Correct	40 ms	14940 KB	Correct.
6	Correct	29 ms	6988 KB	Correct.
7	Correct	46 ms	6372 KB	Correct.
8	Correct	46 ms	1344 KB	Correct.
9	Correct	22 ms	756 KB	Correct.
10	Correct	22 ms	648 KB	Correct.
11	Correct	48 ms	744 KB	Correct.
12	Correct	26 ms	688 KB	Correct.
13	Correct	31 ms	684 KB	Correct.
14	Correct	46 ms	7812 KB	Correct.
15	Correct	45 ms	2308 KB	Correct.
16	Correct	24 ms	724 KB	Correct.
17	Correct	25 ms	796 KB	Correct.
18	Correct	27 ms	692 KB	Correct.
19	Correct	48 ms	656 KB	Correct.
20	Correct	3 ms	468 KB	Correct.
21	Correct	2 ms	520 KB	Correct.
22	Correct	4 ms	980 KB	Correct.

Subtask #8

0.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1240 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-