Submission #550253

#	Time	Username	Problem	Language	Result	Execution time	Memory
550253		Antekb	Treatment Project (JOI20_treatment)	C++14	35 / 100	3079 ms	5968 KiB

treatment

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<17;
const ll INF=1e18;
ll dist[N];
bool vis[N];
int main(){
	int l, n;
	cin>>l>>n;
	vector<pair<pair<int, int>, pair<int, int>> > V(n);
	for(int i=0; i<n; ++i){
		cin>>V[i].nd.st>>V[i].st.st>>V[i].st.nd>>V[i].nd.nd;
		V[i].st.st--;
	}
	for(int i=0; i<n; i++){
		if(V[i].st.st)dist[i]=INF;
		else dist[i]=V[i].nd.nd;
	}
	for(int ii=0; ii<n; ii++){
		int opt=0;
		for(int j=0; j<n; j++){
			//cout<<dist[j]<<" \n"[j==n-1];
			if(!vis[j] && (vis[opt] || dist[j]<dist[opt]))opt=j;
		}
		vis[opt]=1;
		if(V[opt].st.nd==l && dist[opt]!=INF){
			cout<<dist[opt];
			return 0;
		}
		for(int i=0; i<n; i++){
			if(V[i].st.st+V[i].nd.st<=V[opt].st.nd+V[opt].nd.st 
				&& V[i].st.st-V[i].nd.st<=V[opt].st.nd-V[opt].nd.st){
				if(dist[i]>V[i].nd.nd+dist[opt]){
					dist[i]=V[i].nd.nd+dist[opt];
				}
			}
		}
	}
	cout<<-1;
}

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