#include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif const int SQ = 32'000; struct MAIN { vector<set<int>> ach; vector<set<pii>> rev; vector<vector<pii>>g, tr; vector<int> vol; void dfs(int w, int mn) { if(!ach[w].insert(mn).second || mn > SQ) return; for(auto [v, p] : g[w]) if(1ll*mn*p <= vol[v]) dfs(v, mn*p); } void DFS(int w, int upp, ll mn) { if(upp == 0) return; upp = min(upp, vol[w]); auto & s = rev[w]; auto [it, fl] = s.emplace(upp, mn); if(!fl) return; if(auto nxt = next(it); nxt != s.end() && it->second <= nxt->second) { s.erase(it); return; } while(it != s.begin()) { auto prv = prev(it); if(prv->second <= it->second) s.erase(prv); else break; } if(upp < SQ) return; for(auto [v, p] : tr[w]) DFS(v, upp/p, mn*p); } void TEST() { int n,m; cin >> n >> m; ach.resize(n); rev.resize(n); g.resize(n); vol.resize(n); tr.resize(n); for(auto&v:vol) cin >> v; rep(i,0,m) { int a,b,w; cin >> a >> b >> w; --a; --b; g[a].emplace_back(b,w); tr[b].emplace_back(a,w); } dfs(0,1); DFS(n-1,1e9,1); // debug(vol); // rep(i,0,n) debug(i,ach[i]); // rep(i,0,n) debug(i,rev[i]); int res = -1; rep(w,0,n) { auto & ac = ach[w]; auto it = ac.begin(); for(auto [upp, mn] : rev[w]) { while(it != ac.end() && *it <= upp) { res = max(res, *it*mn); ++it; } } } cout << res << '\n'; } }; int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int Z = 1; cin>>Z; while(Z--) MAIN{}.TEST(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <bits/stdc++.h> #define fi first #define sc second #define pb push_back #define rep(i,p,k) for(int i=(p);i<(k);++i) #define forn(i,p,k) for(int i=(p);i<=(k);++i) #define forr(i,k,p) for(int i=(k)-1;i>=(p);--i) #define each(a,b) for(auto&a:b) #define all(v) begin(v), end(v) #define RET(smth) return void(cout<<(smth)<<'\n'); #define sz(v) (int)v.size() using namespace std; using pii = pair<int,int>; using ll = long long; using lll = __int128_t; using Vi = vector<int>; #ifdef DEBUG #include "debug.h" #else #define debug(...) ; #endif const int SQ = 32'000; struct MAIN { vector<set<int>> ach; vector<set<pii>> rev; vector<vector<pii>>g, tr; vector<int> vol; void dfs(int w, int mn) { if(!ach[w].insert(mn).second || mn > SQ) return; for(auto [v, p] : g[w]) if(1ll*mn*p <= vol[v]) dfs(v, mn*p); } void DFS(int w, int upp, ll mn) { if(upp == 0) return; upp = min(upp, vol[w]); auto & s = rev[w]; auto [it, fl] = s.emplace(upp, mn); if(!fl) return; if(auto nxt = next(it); nxt != s.end() && it->second <= nxt->second) { s.erase(it); return; } while(it != s.begin()) { auto prv = prev(it); if(prv->second <= it->second) s.erase(prv); else break; } if(upp < SQ) return; for(auto [v, p] : tr[w]) DFS(v, upp/p, mn*p); } void TEST() { int n,m; cin >> n >> m; ach.resize(n); rev.resize(n); g.resize(n); vol.resize(n); tr.resize(n); for(auto&v:vol) cin >> v; rep(i,0,m) { int a,b,w; cin >> a >> b >> w; --a; --b; g[a].emplace_back(b,w); tr[b].emplace_back(a,w); } dfs(0,1); DFS(n-1,1e9,1); // debug(vol); // rep(i,0,n) debug(i,ach[i]); // rep(i,0,n) debug(i,rev[i]); int res = -1; rep(w,0,n) { auto & ac = ach[w]; auto it = ac.begin(); for(auto [upp, mn] : rev[w]) { while(it != ac.end() && *it <= upp) { res = max(res, *it*mn); ++it; } } } cout << res << '\n'; } }; int main() { #ifndef DEBUG cin.tie(0) -> sync_with_stdio(0); #endif int Z = 1; cin>>Z; while(Z--) MAIN{}.TEST(); return 0; } |