제출 #411681

#제출 시각아이디문제언어결과실행 시간메모리
411681DormiTravelling Merchant (CCO21_day2problem1)C++14
9 / 25
2047 ms32224 KiB
#include <bits/stdc++.h> #pragma GCC optimize "Ofast" #pragma GCC optimize "unroll-loops" #pragma GCC target "sse,sse2,sse3,sse4,abm,avx2,mmx,popcnt" using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template <typename T> int sz(const T &a){return int(a.size());} const int MN=2e5+1; vector<pair<int,pll>> adj[MN]; bool gone[MN]; ll tried[MN]; ll work[MN]; bool dfs(int loc, ll am){ if(am<=tried[loc])return false; if(am>=work[loc])return true; gone[loc]=true; for(auto x:adj[loc]){ if(x.second.first<=am){ if(gone[x.first]){ gone[loc]=false; work[loc]=am; return true; } if(dfs(x.first,am+x.second.second)){ gone[loc]=false; work[loc]=am; return true; } } } tried[loc]=am; gone[loc]=false; return false; } int main(int argc, char *argv[]) { cin.tie(NULL); ios_base::sync_with_stdio(false); int n,m,a,b; cin>>n>>m; ll r,p; for(int i=0;i<m;i++){ cin>>a>>b>>r>>p; adj[a].push_back({b,{r,p}}); } for(int i=1;i<=n;i++)tried[i]=-1,work[i]=LLONG_MAX; for(int i=1;i<=n;i++){ ll lo=0,hi=1e9; while(lo!=hi){ ll mid=(lo+hi)/2; if(dfs(i,mid))hi=mid; else lo=mid+1; } if(lo==1e9)printf("-1%c"," \n"[i==n]); else printf("%lli%c",lo," \n"[i==n]); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...