oj.uz

Submission #289555

# Submission time Handle Problem Language Result Execution time Memory
289555 2020-09-02T18:08:36 Z TadijaSebez Treatment Project (JOI20_treatment) C++11
35 / 100
 2346 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
const int N=100050;
const ll inf=9e18;
struct project{
	int t,l,r,c;
	project(){}
	project(int a,int b,int d,int e):t(a),l(b),r(d),c(e){}
	bool operator < (project b){return l+r<b.l+b.r||(l+r==b.l+b.r&&t<b.t);}
}pro[N];
vector<pii> E[N];
void AddEdge(int u,int v){E[u].pb({v,pro[v].c});}
ll dist[N];
void Dijkstra(int s,int t){
	priority_queue<pair<ll,int>> pq;
	pq.push({0,s});
	for(int i=s+1;i<=t;i++)dist[i]=inf;
	while(pq.size()){
		ll d=-pq.top().first;
		int u=pq.top().second;
		pq.pop();
		if(dist[u]!=d)continue;
		for(auto e:E[u]){
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({-dist[v],v});
			}
		}
	}
}
int n,m;
bool can_merge(int j,int i){
	int delta_t=abs(pro[i].t-pro[j].t);
	if(delta_t>pro[j].r+1-pro[i].l)return 0;
	return 1;
}
int main(){
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
	for(int i=1;i<=m;i++){
		if(pro[i].l==1)AddEdge(0,i);
		for(int j=1;j<=m;j++)if(i!=j){
			if(can_merge(i,j))AddEdge(i,j);
			if(can_merge(j,i))AddEdge(j,i);
		}
		if(pro[i].r==n)AddEdge(i,m+1);
	}
	Dijkstra(0,m+1);
	ll ans=dist[m+1];
	printf("%lld\n",ans==inf?-1:ans);
	return 0;
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
treatment.cpp:43:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 2346 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2728 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Correct 799 ms 306880 KB Output is correct
21 Correct 785 ms 305784 KB Output is correct
22 Correct 101 ms 8440 KB Output is correct
23 Correct 101 ms 8440 KB Output is correct
24 Correct 532 ms 188152 KB Output is correct
25 Correct 372 ms 136720 KB Output is correct
26 Correct 336 ms 131448 KB Output is correct
27 Correct 383 ms 158096 KB Output is correct
28 Correct 530 ms 186488 KB Output is correct
29 Correct 371 ms 134264 KB Output is correct
30 Correct 367 ms 150136 KB Output is correct
31 Correct 374 ms 161912 KB Output is correct
32 Correct 731 ms 250192 KB Output is correct
33 Correct 1087 ms 432124 KB Output is correct
34 Correct 700 ms 257972 KB Output is correct
35 Correct 739 ms 252536 KB Output is correct
36 Correct 1073 ms 431736 KB Output is correct
37 Correct 698 ms 257200 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 2346 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -