結果
| 問題 |
No.2523 Trick Flower
|
| コンテスト | |
| ユーザー |
 hotman78
|
| 提出日時 | 2023-10-27 23:00:15 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 12,747 bytes |
| コンパイル時間 | 13,510 ms |
| コンパイル使用メモリ | 296,576 KB |
| 最終ジャッジ日時 | 2025-02-17 15:44:52 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 RE * 23 |
ソースコード
// author: hotman78
// date: 2023/10/27-23:00:09
// --- begin raw code -----------------
// #include"cpplib/util/template.hpp"
// #include"cpplib/math/binary_search.hpp"
// #include"cpplib/dsu/union_find.hpp"
//
// int main(){
// lint n;
// cin>>n;
// vector<lint> a(n),b(n),c(n);
// rep(i,n)cin>>a[i];
// rep(i,n)cin>>b[i];
// rep(i,n)cin>>c[i];
// rep(i,n)c[i]--;
// vec in_cycle(n,true);
// {
// stack<lint> s;
// vec used(n);
// rep(i,n){
// used[c[i]]++;
// }
// rep(i,n)if(used[i]==0)s.push(i);
// while(!s.empty()){
// lint v=s.top();s.pop();
// in_cycle[v]=false;
// used[c[v]]--;
// if(used[c[v]]==0)s.push(c[v]);
// }
// }
// UF uf(n);
// rep(i,n){
// if(in_cycle[i])uf.unite(i,c[i]);
// }
// auto f=[&](lint x){
// stack<lint> s;
// vec used(n);
// vector<__int128_t> demand(n);
// rep(i,n)used[c[i]]++;
// rep(i,n)if(used[i]==0)s.push(i);
// while(!s.empty()){
// lint v=s.top();s.pop();
// if(c[v]==v){
// if(demand[v]+__int128_t(b[v])*x-a[v]>0){
// return false;
// }
// continue;
// }
// used[c[v]]--;
// if(used[c[v]]==0){
// assert(!in_cycle[c[v]]);
// demand[c[v]]+=max<__int128_t>(0LL,__int128_t(b[v])*x+demand[v]-a[v]);
// s.push(c[v]);
// }else{
// assert(in_cycle[c[v]]);
// demand[uf.root(c[v])]+=max<__int128_t>(0LL,__int128_t(b[v])*x+demand[v]-a[v]);
// }
// }
// rep(i,n){
// if(in_cycle[i]){
// demand[uf.root(i)]+=__int128_t(b[i])*x-a[i];
// }
// }
// rep(i,n){
// if(in_cycle[i]){
// // cerr<<i<<":"<<demand[uf.root(i)]<<endl;
// if(demand[uf.root(i)]>0){
// return false;
// }
// }
// }
// return true;
// };
// // cerr<<f(3)<<endl;
// cout<<bs(0LL,1LL<<60,f)<<endl;
// }
// --- end raw code -----------------
#line 2 "cpplib/util/template.hpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#line 1 "cpplib/util/ioutil.hpp"
// template <class Head,class... Args>
// std::ostream& output(std::ostream& out,const Head& head,const Args&... args){
// out>>head;
// return output(head,args...);
// }
// template <class Head>
// std::ostream& output(std::ostream& out,const Head& head){
// out>>head;
// return out;
// }
template <typename T, typename E>
std::ostream &operator<<(std::ostream &out, std::pair<T, E> v) {
out << "(" << v.first << "," << v.second << ")";
return out;
}
// template <class... Args>
// ostream& operator<<(ostream& out,std::tuple<Args...>v){
// std::apply(output,v);
// return out;
// }
#line 11 "cpplib/util/template.hpp"
struct __INIT__ {
__INIT__() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} __INIT__;
typedef long long lint;
constexpr long long INF = 1LL << 60;
constexpr int IINF = 1 << 30;
constexpr double EPS = 1e-10;
#ifndef REACTIVE
#define endl '\n';
#endif
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
#define output(t) \
{ \
bool f = 0; \
for (auto val : (t)) { \
cout << (f ? " " : "") << val; \
f = 1; \
} \
cout << endl; \
}
#define output2(t) \
{ \
for (auto i : t) \
output(i); \
}
#define debug(t) \
{ \
bool f = 0; \
for (auto i : t) { \
cerr << (f ? " " : "") << i; \
f = 1; \
} \
cerr << endl; \
}
#define debug2(t) \
{ \
for (auto i : t) \
debug(i); \
}
#define loop(n) for (long long _ = 0; _ < (long long)(n); ++_)
#define _overload4(_1, _2, _3, _4, name, ...) name
#define __rep(i, a) repi(i, 0, a, 1)
#define _rep(i, a, b) repi(i, a, b, 1)
#define repi(i, a, b, c) \
for (long long i = (long long)(a); i < (long long)(b); i += c)
#define rep(...) _overload4(__VA_ARGS__, repi, _rep, __rep)(__VA_ARGS__)
#define _overload3_rev(_1, _2, _3, name, ...) name
#define _rep_rev(i, a) repi_rev(i, 0, a)
#define repi_rev(i, a, b) \
for (long long i = (long long)(b)-1; i >= (long long)(a); --i)
#define rrep(...) _overload3_rev(__VA_ARGS__, repi_rev, _rep_rev)(__VA_ARGS__)
#define all(n) begin(n), end(n)
template <typename T, typename E> bool chmin(T &s, const E &t) {
bool res = s > t;
s = min<T>(s, t);
return res;
}
template <typename T, typename E> bool chmax(T &s, const E &t) {
bool res = s < t;
s = max<T>(s, t);
return res;
}
const vector<lint> dx = {1, 0, -1, 0, 1, 1, -1, -1};
const vector<lint> dy = {0, 1, 0, -1, 1, -1, 1, -1};
#define SUM(v) accumulate(all(v), 0LL)
#if __cplusplus >= 201703L
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
if constexpr (sizeof...(args) == 0)
return vector<T>(arg, x);
else
return vector(arg, make_vector<T>(x, args...));
}
#endif
#define extrep(v, ...) for (auto v : __MAKE_MAT__({__VA_ARGS__}))
#define bit(n, a) ((n >> a) & 1)
vector<vector<long long>> __MAKE_MAT__(vector<long long> v) {
if (v.empty())
return vector<vector<long long>>(1, vector<long long>());
long long n = v.back();
v.pop_back();
vector<vector<long long>> ret;
vector<vector<long long>> tmp = __MAKE_MAT__(v);
for (auto e : tmp)
for (long long i = 0; i < n; ++i) {
ret.push_back(e);
ret.back().push_back(i);
}
return ret;
}
using graph = vector<vector<int>>;
template <typename T> using graph_w = vector<vector<pair<int, T>>>;
#if __cplusplus >= 201703L
constexpr inline long long powll(long long a, long long b) {
long long res = 1;
while (b--)
res *= a;
return res;
}
#endif
template <typename T, typename E>
pair<T, E> &operator+=(pair<T, E> &s, const pair<T, E> &t) {
s.first += t.first;
s.second += t.second;
return s;
}
template <typename T, typename E>
pair<T, E> &operator-=(pair<T, E> &s, const pair<T, E> &t) {
s.first -= t.first;
s.second -= t.second;
return s;
}
template <typename T, typename E>
pair<T, E> operator+(const pair<T, E> &s, const pair<T, E> &t) {
auto res = s;
return res += t;
}
template <typename T, typename E>
pair<T, E> operator-(const pair<T, E> &s, const pair<T, E> &t) {
auto res = s;
return res -= t;
}
#define BEGIN_STACK_EXTEND(size) \
void *stack_extend_memory_ = malloc(size); \
void *stack_extend_origin_memory_; \
char *stack_extend_dummy_memory_ = (char *)alloca( \
(1 + (int)(((long long)stack_extend_memory_) & 127)) * 16); \
*stack_extend_dummy_memory_ = 0; \
asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp" \
: "=b"(stack_extend_origin_memory_) \
: "a"((char *)stack_extend_memory_ + (size)-1024));
#define END_STACK_EXTEND \
asm volatile("mov %%rax, %%rsp" ::"a"(stack_extend_origin_memory_)); \
free(stack_extend_memory_);
int floor_pow(int n) { return n ? 31 - __builtin_clz(n) : 0; }
#line 3 "cpplib/math/binary_search.hpp"
/**
* @brief 二分探索
*/
template <typename T = long long, typename F> T bs(T ok, T ng, F func) {
while (abs(ok - ng) > 1) {
T mid = (ok + ng) / 2;
if (func(mid))
ok = mid;
else
ng = mid;
}
return ok;
}
#line 1 "cpplib/dsu/union_find.hpp"
/**
* @brief Union Find
* @see
* https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0
*/
class UF {
public:
vector<int> data;
int sz;
public:
UF(int sz) : sz(sz) { data.resize(sz, -1); }
bool unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return 0;
if (data[x] > data[y])
swap(x, y);
data[x] += data[y];
data[y] = x;
sz--;
return 1;
}
inline int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
inline bool same(int x, int y) { return root(x) == root(y); }
inline int size() { return sz; }
inline int size(int x) { return -data[root(x)]; }
};
#line 4 "main.cpp"
int main() {
lint n;
cin >> n;
vector<lint> a(n), b(n), c(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> b[i];
rep(i, n) cin >> c[i];
rep(i, n) c[i]--;
vec in_cycle(n, true);
{
stack<lint> s;
vec used(n);
rep(i, n) { used[c[i]]++; }
rep(i, n) if (used[i] == 0) s.push(i);
while (!s.empty()) {
lint v = s.top();
s.pop();
in_cycle[v] = false;
used[c[v]]--;
if (used[c[v]] == 0)
s.push(c[v]);
}
}
UF uf(n);
rep(i, n) {
if (in_cycle[i])
uf.unite(i, c[i]);
}
auto f = [&](lint x) {
stack<lint> s;
vec used(n);
vector<__int128_t> demand(n);
rep(i, n) used[c[i]]++;
rep(i, n) if (used[i] == 0) s.push(i);
while (!s.empty()) {
lint v = s.top();
s.pop();
if (c[v] == v) {
if (demand[v] + __int128_t(b[v]) * x - a[v] > 0) {
return false;
}
continue;
}
used[c[v]]--;
if (used[c[v]] == 0) {
assert(!in_cycle[c[v]]);
demand[c[v]] += max<__int128_t>(0LL, __int128_t(b[v]) * x +
demand[v] - a[v]);
s.push(c[v]);
} else {
assert(in_cycle[c[v]]);
demand[uf.root(c[v])] += max<__int128_t>(
0LL, __int128_t(b[v]) * x + demand[v] - a[v]);
}
}
rep(i, n) {
if (in_cycle[i]) {
demand[uf.root(i)] += __int128_t(b[i]) * x - a[i];
}
}
rep(i, n) {
if (in_cycle[i]) {
// cerr<<i<<":"<<demand[uf.root(i)]<<endl;
if (demand[uf.root(i)] > 0) {
return false;
}
}
}
return true;
};
// cerr<<f(3)<<endl;
cout << bs(0LL, 1LL << 60, f) << endl;
}