Submission #445914

#	Time	Username	Problem	Language	Result	Execution time	Memory
445914		kig9981	Treatment Project (JOI20_treatment)	C++17	0 / 100	3077 ms	2492 KiB

treatment

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const long long INF=0x3f3f3f3f3f3f3f3fLL;
vector<tuple<int,int,int,int,int>> A;
vector<int> adj[5000];
int chk[5000];
long long dist[5000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	priority_queue<pair<long long,int>> Q;
	long long ans;
	cin>>N>>M; A.resize(M);
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(l--==1) chk[i]|=1;
		if(r==N) chk[i]|=2;
		tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
		for(int j=0;j<i;j++) {
			auto[x1,y1,x2,y2,t]=A[j];
			if(max(x1,t)<=min(x2,r) && max(y1,l)<=min(y2,aa)) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	for(int i=0;i<M;i++) if(chk[i]&1) Q.emplace(-(dist[i]=get<4>(A[i])),i);
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		for(auto n: adj[c]) if(dist[n]==INF && dist[n]>dist[c]+get<4>(A[n])) {
			dist[n]=dist[c]+get<4>(A[n]);
			Q.emplace(-dist[n],n);
		}
	}
	ans=INF;
	for(int i=0;i<M;i++) if(chk[i]&2) ans=min(ans,dist[i]);
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61