# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
570549 | 2022-05-30T12:21:56 Z | codebuster_10 | Robot (JOI21_ho_t4) | C++17 | 1218 ms | 102580 KB |
#include <bits/stdc++.h> #define int int64_t //be careful about this using namespace std; #define vt vector #define ar array #define pr pair #define f first #define s second #define pb push_back #define eb emplace_back #define fr(i,a,b) for(int i = a; i < b; ++i) #define rf(i,a,b) for(int i = b-1; i >= a; --i) #define all(x) x.begin(),x.end() #define mem(a,b) memset(a,b,sizeof(a)) namespace IN{ template<class T> void re(vector<T> &A); template<class S,class T> void re(pair<S,T> &A); template<class T,size_t N> void re(array<T,N> &A); template<class T> void re(T& x){ cin >> x;} template<class H, class... T> void re(H& h, T&... t){ re(h); re(t...);} template<class T> void re(vector<T> &A){ for(auto& x : A) re(x);} template<class S,class T> void re(pair<S,T> &A){ re(A.first); re(A.second);} template<class T,size_t N> void re(array<T,N> &A){ for(int i = 0; i < N; ++i) re(A[i]);} } namespace OUT{ template<class T> void __p(const T& a){ cout<<a; } template<class T, class F> void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<class T, size_t N> void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; } template<class T> void __p(const vector<T>& a){ cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; } template<class T, class ...Arg> void __p(T a1, Arg ...a){__p(a1); __p(a...); } template<class Arg1> void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; } template<class Arg1, class ... Args> void __f(const char *ss, Arg1 &&arg1, Args &&... args){ int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0)); const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);} #define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__) } namespace FUN{ void IO(string s = ""){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.precision(20); cout << fixed; if(!s.empty()){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } const auto start_time = chrono::high_resolution_clock::now(); void output_run_time(){ // will work for ac,cc&&cf. #ifndef ONLINE_JUDGE auto end_time = chrono::high_resolution_clock::now(); chrono::duration<double> diff = end_time-start_time; cout << "\n\n\nTime Taken : " << diff.count(); #endif } template<class T> bool ckmin(T& a, const T& b){ return b < a ? a = b, true : false; } template<class T> bool ckmax(T& a, const T& b){ return a < b ? a = b, true : false; } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int my_rand(int L, int R){ return uniform_int_distribution<int>(L,R)(rng); } template<class T> int sz(const T& x){ return int(x.size()); } template<class T> int lb(const vector<T>& vec,const T& val){ return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); } template<class T> int ub(const vector<T>& vec,const T& val){ return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); } constexpr int dx[4] = {1,0,-1,0}; constexpr int dy[4] = {0,1,0,-1}; constexpr char dr[4] = {'D','R','U','L'}; constexpr long long INFLL1 = 1e16, INFLL2 = 9e18; constexpr int INF = 2e9; template<class T> vector<T> V(int n,T val){ return vector<T> (n,val); } template<class T> vector<vector<T>> V(int n,int m,T val){ return vector<vector<T>> (n,vector<T> (m,val)); } template<class T> vector<vector<vector<T>>> V(int n,int m,int k,T val){ return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val))); } } using namespace IN; using namespace OUT; using namespace FUN; struct E{ int u,c,p; }; const int N = 1e5 + 7; int dp[N]; map<int,int> dp2[N],tot[N]; map<int,vt<E>> gc[N]; vt<E> g[N]; signed main(){ IO(); int n,m; re(n,m); fr(e,0,m){ int u,v,c,p; re(u,v,c,p); --u,--v,--c; g[u].pb({v,c,p}); g[v].pb({u,c,p}); gc[u][c].pb({v,c,p}); gc[v][c].pb({u,c,p}); tot[u][c] += p; tot[v][c] += p; } priority_queue<tuple<int,int,int>> pq; fr(i,0,n){ dp[i] = INFLL1; } dp[0] = 0; pq.push({-dp[0],0,-1}); while(!pq.empty()){ auto [d,i,f] = pq.top(); pq.pop(); if(f < 0){ if(-d != dp[i]) continue; for(auto [j,c,p] : g[i]){ if(ckmin(dp[j],dp[i]+min(p,tot[i][c]-p))) pq.push({-dp[j],j,-1}); if(!dp2[j].count(c) || ckmin(dp2[j][c],dp[i])){ dp2[j][c] = dp[i]; pq.push({-dp2[j][c],j,c}); } } }else{ if(-d != dp2[i][f]) continue; for(auto [j,c,p] : gc[i][f]){ assert(c == f); if(ckmin(dp[j],dp2[i][f]+tot[i][f]-p)) pq.push({-dp[j],j,-1}); } } } cout << (dp[n-1] == INFLL1 ? int(-1) : dp[n-1]); // output_run_time(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 16724 KB | Output is correct |
2 | Correct | 9 ms | 16744 KB | Output is correct |
3 | Correct | 9 ms | 16668 KB | Output is correct |
4 | Correct | 9 ms | 16772 KB | Output is correct |
5 | Correct | 11 ms | 16716 KB | Output is correct |
6 | Correct | 10 ms | 16852 KB | Output is correct |
7 | Correct | 10 ms | 16980 KB | Output is correct |
8 | Correct | 9 ms | 16852 KB | Output is correct |
9 | Correct | 15 ms | 17480 KB | Output is correct |
10 | Correct | 13 ms | 17492 KB | Output is correct |
11 | Correct | 13 ms | 17236 KB | Output is correct |
12 | Correct | 12 ms | 17240 KB | Output is correct |
13 | Correct | 11 ms | 17236 KB | Output is correct |
14 | Correct | 12 ms | 17320 KB | Output is correct |
15 | Correct | 10 ms | 17108 KB | Output is correct |
16 | Correct | 11 ms | 17236 KB | Output is correct |
17 | Correct | 11 ms | 17236 KB | Output is correct |
18 | Correct | 10 ms | 16960 KB | Output is correct |
19 | Correct | 12 ms | 17108 KB | Output is correct |
20 | Correct | 11 ms | 17168 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 241 ms | 42200 KB | Output is correct |
2 | Correct | 97 ms | 29272 KB | Output is correct |
3 | Correct | 253 ms | 44304 KB | Output is correct |
4 | Correct | 164 ms | 33760 KB | Output is correct |
5 | Correct | 1157 ms | 96880 KB | Output is correct |
6 | Correct | 802 ms | 89568 KB | Output is correct |
7 | Correct | 379 ms | 71552 KB | Output is correct |
8 | Correct | 573 ms | 70296 KB | Output is correct |
9 | Correct | 570 ms | 70328 KB | Output is correct |
10 | Correct | 421 ms | 60348 KB | Output is correct |
11 | Correct | 197 ms | 43120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 16724 KB | Output is correct |
2 | Correct | 9 ms | 16744 KB | Output is correct |
3 | Correct | 9 ms | 16668 KB | Output is correct |
4 | Correct | 9 ms | 16772 KB | Output is correct |
5 | Correct | 11 ms | 16716 KB | Output is correct |
6 | Correct | 10 ms | 16852 KB | Output is correct |
7 | Correct | 10 ms | 16980 KB | Output is correct |
8 | Correct | 9 ms | 16852 KB | Output is correct |
9 | Correct | 15 ms | 17480 KB | Output is correct |
10 | Correct | 13 ms | 17492 KB | Output is correct |
11 | Correct | 13 ms | 17236 KB | Output is correct |
12 | Correct | 12 ms | 17240 KB | Output is correct |
13 | Correct | 11 ms | 17236 KB | Output is correct |
14 | Correct | 12 ms | 17320 KB | Output is correct |
15 | Correct | 10 ms | 17108 KB | Output is correct |
16 | Correct | 11 ms | 17236 KB | Output is correct |
17 | Correct | 11 ms | 17236 KB | Output is correct |
18 | Correct | 10 ms | 16960 KB | Output is correct |
19 | Correct | 12 ms | 17108 KB | Output is correct |
20 | Correct | 11 ms | 17168 KB | Output is correct |
21 | Correct | 241 ms | 42200 KB | Output is correct |
22 | Correct | 97 ms | 29272 KB | Output is correct |
23 | Correct | 253 ms | 44304 KB | Output is correct |
24 | Correct | 164 ms | 33760 KB | Output is correct |
25 | Correct | 1157 ms | 96880 KB | Output is correct |
26 | Correct | 802 ms | 89568 KB | Output is correct |
27 | Correct | 379 ms | 71552 KB | Output is correct |
28 | Correct | 573 ms | 70296 KB | Output is correct |
29 | Correct | 570 ms | 70328 KB | Output is correct |
30 | Correct | 421 ms | 60348 KB | Output is correct |
31 | Correct | 197 ms | 43120 KB | Output is correct |
32 | Correct | 181 ms | 45288 KB | Output is correct |
33 | Correct | 222 ms | 43508 KB | Output is correct |
34 | Correct | 494 ms | 64740 KB | Output is correct |
35 | Correct | 383 ms | 53944 KB | Output is correct |
36 | Correct | 360 ms | 59040 KB | Output is correct |
37 | Correct | 416 ms | 65628 KB | Output is correct |
38 | Correct | 429 ms | 77768 KB | Output is correct |
39 | Correct | 206 ms | 53152 KB | Output is correct |
40 | Correct | 576 ms | 71668 KB | Output is correct |
41 | Correct | 622 ms | 72032 KB | Output is correct |
42 | Correct | 617 ms | 78596 KB | Output is correct |
43 | Correct | 273 ms | 47364 KB | Output is correct |
44 | Correct | 515 ms | 63764 KB | Output is correct |
45 | Correct | 460 ms | 62952 KB | Output is correct |
46 | Correct | 387 ms | 62108 KB | Output is correct |
47 | Correct | 381 ms | 63384 KB | Output is correct |
48 | Correct | 1218 ms | 102580 KB | Output is correct |