oj.uz

답안 #750850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750850 2023-05-30T11:47:26 Z josanneo22 사이버랜드 (APIO23_cyberland) C++17
97 / 100
 1030 ms 2097152 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) {
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 448 KB Correct.
2 Correct 31 ms 460 KB Correct.

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 996 KB Correct.
2 Correct 29 ms 1020 KB Correct.
3 Correct 27 ms 984 KB Correct.
4 Correct 30 ms 908 KB Correct.
5 Correct 29 ms 984 KB Correct.
6 Correct 25 ms 6244 KB Correct.
7 Correct 35 ms 6044 KB Correct.
8 Correct 14 ms 12116 KB Correct.
9 Correct 26 ms 612 KB Correct.
10 Correct 26 ms 596 KB Correct.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 920 KB Correct.
2 Correct 25 ms 1060 KB Correct.
3 Correct 27 ms 1040 KB Correct.
4 Correct 25 ms 604 KB Correct.
5 Correct 25 ms 616 KB Correct.
6 Correct 6 ms 5076 KB Correct.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 35008 KB Correct.
2 Correct 34 ms 928 KB Correct.
3 Correct 24 ms 948 KB Correct.
4 Correct 25 ms 1024 KB Correct.
5 Correct 28 ms 596 KB Correct.

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 964 KB Correct.
2 Correct 31 ms 936 KB Correct.
3 Correct 29 ms 924 KB Correct.
4 Correct 31 ms 5936 KB Correct.
5 Correct 26 ms 596 KB Correct.

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 932 KB Correct.
2 Correct 26 ms 996 KB Correct.
3 Correct 63 ms 45700 KB Correct.
4 Correct 28 ms 3988 KB Correct.
5 Correct 25 ms 596 KB Correct.
6 Correct 26 ms 912 KB Correct.

Subtask #7
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 904 KB Correct.
2 Correct 5 ms 1236 KB Correct.
3 Correct 57 ms 37964 KB Correct.
4 Correct 51 ms 10060 KB Correct.
5 Correct 43 ms 23772 KB Correct.
6 Correct 29 ms 9668 KB Correct.
7 Correct 50 ms 10040 KB Correct.
8 Correct 53 ms 2008 KB Correct.
9 Correct 26 ms 972 KB Correct.
10 Correct 26 ms 912 KB Correct.
11 Correct 51 ms 956 KB Correct.
12 Correct 28 ms 888 KB Correct.
13 Correct 31 ms 1032 KB Correct.
14 Correct 59 ms 10760 KB Correct.
15 Correct 51 ms 3676 KB Correct.
16 Correct 28 ms 964 KB Correct.
17 Correct 29 ms 988 KB Correct.
18 Correct 28 ms 924 KB Correct.
19 Correct 55 ms 908 KB Correct.
20 Correct 3 ms 508 KB Correct.
21 Correct 3 ms 876 KB Correct.
22 Correct 3 ms 1108 KB Correct.

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1030 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -