oj.uz

Submission #331988

# Submission time Handle Problem Language Result Execution time Memory
331988 2020-12-01T01:06:48 Z YJU Treatment Project (JOI20_treatment) C++14
35 / 100
 1121 ms 524288 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e5+5;
const ll K=350;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,dis[N],C[N],T[N],L[N],R[N],ans=INF;
vector<ll> v[N];

priority_queue<pll,vector<pll>,greater<pll> > pq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,m){
		cin>>T[i]>>L[i]>>R[i]>>C[i];
	}
	REP1(i,m)REP1(j,m){
		if(T[i]>=T[j]&&R[i]-T[i]>=L[j]-T[j]-1){
			v[i].pb(j);
		}else if(T[i]<T[j]&&R[i]+T[i]>=L[j]+T[j]-1){
			v[i].pb(j);
		}
	}
	REP1(i,m){
		if(L[i]==1)pq.push(mp(dis[i]=C[i],i));
		else dis[i]=INF;
	}
	while(SZ(pq)){
		ll x=pq.top().Y,y=pq.top().X;pq.pop();
		if(y>dis[x])continue;
		//cout<<dis[x]<<" "<<x<<"\n";
		for(auto i:v[x]){
			if(dis[i]>y+C[i]){
				//cout<<x<<"->"<<i<<"\n";
				pq.push(mp(dis[i]=y+C[i],i));
			}
		}
	}
	REP1(i,m)if(R[i]==n)ans=min(ans,dis[i]);
	cout<<(ans==INF?-1:ans)<<"\n";
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1121 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 2 ms 2668 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 341 ms 132076 KB Output is correct
21 Correct 321 ms 131564 KB Output is correct
22 Correct 143 ms 5740 KB Output is correct
23 Correct 142 ms 5740 KB Output is correct
24 Correct 216 ms 95748 KB Output is correct
25 Correct 142 ms 66412 KB Output is correct
26 Correct 135 ms 63432 KB Output is correct
27 Correct 143 ms 77292 KB Output is correct
28 Correct 214 ms 95116 KB Output is correct
29 Correct 139 ms 65644 KB Output is correct
30 Correct 133 ms 73836 KB Output is correct
31 Correct 142 ms 79084 KB Output is correct
32 Correct 331 ms 122988 KB Output is correct
33 Correct 336 ms 191748 KB Output is correct
34 Correct 317 ms 122348 KB Output is correct
35 Correct 332 ms 123244 KB Output is correct
36 Correct 364 ms 191468 KB Output is correct
37 Correct 317 ms 122220 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 1121 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -