제출 #1241779

#제출 시각아이디문제언어결과실행 시간메모리
1241779MinbaevDreaming (IOI13_dreaming)C++20
18 / 100
39 ms17584 KiB
#include "dreaming.h" //#include "grader.c" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define ar array #define mrand(a, b) uniform_int_distribution<int>(a, b)(rng) template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); namespace FAST { template<typename T, typename F> istream &operator>>(istream &cin, pair<T, F> &p) { cin >> p.first >> p.second; return cin; } template<typename T, typename F> ostream &operator<<(ostream &cout, pair<T, F> &p) { cout << p.first << ' ' << p.second; return cout; } template<typename T> istream &operator>>(istream &cin, vector<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, vector<T> &a) { for (T i: a) cout << i << ' '; return cout; } template<typename T> istream &operator>>(istream &cin, deque<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, deque<T> &a) { for (T i: a) cout << i << ' '; return cout; } } using namespace FAST; const long long inf = 1e17 + 7; const int mod = 1e9 + 7; const int md = 998244353; vector<ar<int,2>>g[100005], cycle; vector<int>mx(100005), vis(100005); void dfs(int x, int pr){ vis[x] = 1; for(auto [to, cost] : g[x]){ if(to == pr)continue; dfs(to, x); umax(mx[x], mx[to] + cost); } } void fmx(int x, int pr, int a){ umax(mx[x], a); cycle.pb({mx[x], x}); vis[x] = 1; vector<ar<int,2>>vs; for(auto [to, cost] : g[x]){ if(to == pr)continue; vs.pb({mx[to] + cost, to}); } sort(all(vs)); reverse(all(vs)); // if(x == 1){ // for(auto to:vs)cout << to[0] << " " << to[1] << "\n"; // cout << "\n"; // } for(auto [to, cost] : g[x]){ if(to == pr)continue; if(to == vs[0][1]){ if(vs.size() > 1) fmx(to, x, max(a, vs[1][0]) + cost); else fmx(to, x, a + cost); } else{ fmx(to, x, max(a, vs[0][0]) + cost); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { // cout << 1 << "\n"; // exit(0); for(int i = 0;i<M;i++){ g[A[i]].pb({B[i], T[i]}); g[B[i]].pb({A[i], T[i]}); } for(int i = 0;i<N;i++){ if(vis[i])continue; dfs(i, -1); } // cout << 0 << "\n"; // exit(0); for(int i = 0;i<N;i++){ vis[i] = 0; } vector<int>vs; // cout << mx[5] << "\n"; for(int i = 0;i<N;i++){ if(vis[i])continue; cycle.clear(); fmx(i, -1, 0); sort(all(cycle)); vs.pb(cycle[0][0]); // cout << cycle[0][0] << "\n"; } sort(all(vs)); reverse(all(vs)); int u = 0; // return 0; if(vs.size() == 1)return vs[0]; else if(vs.size() == 2)return vs[0] + vs[1] + L; else return max(vs[0] + vs[1] + L, vs[1] + vs[2] + 2 * L); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...