Submission #420337

#TimeUsernameProblemLanguageResultExecution timeMemory
420337alishahali1382Treatment Project (JOI20_treatment)C++17
0 / 100
3075 ms3012 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O2") using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; typedef pair<pii, int> piii; #define debug(x) {cerr<<#x<<"="<<x<<"\n";} #define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";} #define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";} #define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";} #define pb push_back #define all(x) x.begin(), x.end() #define kill(x) return cout<<x<<"\n", 0; #define SZ(x) ((int)x.size()) const int inf=1000010000; const ll INF=10000000000100000ll; // 1e16 const int mod=1000000007; const int MAXN=100010; int n, m, q, k, u, v, x, y, t; int L[MAXN], R[MAXN], T[MAXN], C[MAXN]; int mark[MAXN]; ll dist[MAXN], ans=INF; priority_queue<pll, vector<pll>, greater<pll>> pq; inline bool upd(ll &x, ll y){ if (x<=y) return 0; x=y; return 1; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(dist, 63, sizeof(dist)); cin>>n>>m; for (int i=1; i<=m; i++){ cin>>T[i]>>L[i]>>R[i]>>C[i]; L[i]--; if (!L[i]) pq.push({dist[i]=C[i], i}); } while (pq.size()){ int v=pq.top().second; pq.pop(); mark[v]=2; for (int i=1; i<=m; i++) if (!mark[i]){ bool ok=0; if (T[i]<=T[v]){ ok=(L[i]+(T[v]-T[i])<=R[v]); } else{ ok=(L[i]<=R[v]-(T[i]-T[v])); } if (!ok) continue ; mark[i]=upd(dist[i], dist[v]+C[i]); if (mark[i]) pq.push({dist[i], i}); assert(mark[i]); } } for (int i=1; i<=m; i++) if (R[i]==n) upd(ans, dist[i]); if (ans>=INF) ans=-1; cout<<ans<<"\n"; return 0; } /* 10 5 2 5 10 3 1 1 6 5 5 2 8 3 7 6 10 4 4 1 3 1 10 5 2 6 10 3 1 1 5 5 5 2 7 3 8 6 10 4 4 1 3 1 10 5 1 5 10 4 1 1 6 5 1 4 8 3 1 6 10 3 1 1 3 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...