oj.uz

답안 #423910

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423910 2021-06-11T14:06:09 Z jamezzz 치료 계획 (JOI20_treatment) C++17
0 / 100
 118 ms 11920 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;

#define maxn 100005

int n,m,t[maxn],l[maxn],r[maxn],c[maxn];
ll dist[maxn];
vector<int> d;
vector<ii> AL[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;

int main(){
	sf("%d%d",&n,&m);
	d.pb(1);d.pb(n+1);
	for(int i=0;i<m;++i){
		sf("%d%d%d%d",&t[i],&l[i],&r[i],&c[i]);
		d.pb(l[i]);d.pb(r[i]+1);
	}
	sort(all(d));
	d.erase(unique(all(d)),d.end());
	for(int i=0;i<m;++i){
		l[i]=lower_bound(all(d),l[i])-d.begin();
		r[i]=lower_bound(all(d),r[i]+1)-d.begin();
		AL[l[i]].pb(r[i],c[i]);
	}
	n=d.size();
	for(int i=0;i<n;++i){
		dist[i]=LINF;
		if(i!=0)AL[i].pb(i-1,0);
	}
	dist[0]=0;
	pq.push(li(0,0));
	while(!pq.empty()){
		ll d;int u;tie(d,u)=pq.top();pq.pop();
		if(d>dist[u])continue;
		for(ii pr:AL[u]){
			if(dist[pr.fi]>dist[u]+pr.se){
				dist[pr.fi]=dist[u]+pr.se;
				pq.push(li(dist[pr.fi],pr.fi));
			}
		}
	}
	if(dist[n-1]==LINF)pf("-1\n");
	else pf("%lld\n",dist[n-1]);
}

/*
10 5
1 5 10 3
1 1 6 5
1 2 8 3
1 6 10 4
1 1 3 1
*/

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:24:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  sf("%d%d",&n,&m);
      |    ^
treatment.cpp:27:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   sf("%d%d%d%d",&t[i],&l[i],&r[i],&c[i]);
      |     ^

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 10668 KB Output is correct
2 Correct 118 ms 10688 KB Output is correct
3 Correct 106 ms 9556 KB Output is correct
4 Correct 88 ms 9564 KB Output is correct
5 Correct 55 ms 7564 KB Output is correct
6 Correct 64 ms 7916 KB Output is correct
7 Correct 70 ms 8208 KB Output is correct
8 Correct 57 ms 7604 KB Output is correct
9 Correct 65 ms 7820 KB Output is correct
10 Correct 70 ms 8600 KB Output is correct
11 Runtime error 66 ms 11920 KB Execution killed with signal 7
12 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 3 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Incorrect 3 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 10668 KB Output is correct
2 Correct 118 ms 10688 KB Output is correct
3 Correct 106 ms 9556 KB Output is correct
4 Correct 88 ms 9564 KB Output is correct
5 Correct 55 ms 7564 KB Output is correct
6 Correct 64 ms 7916 KB Output is correct
7 Correct 70 ms 8208 KB Output is correct
8 Correct 57 ms 7604 KB Output is correct
9 Correct 65 ms 7820 KB Output is correct
10 Correct 70 ms 8600 KB Output is correct
11 Runtime error 66 ms 11920 KB Execution killed with signal 7
12 Halted 0 ms 0 KB -