Submission #1226042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226042		boclobanchat	Robot (JOI21_ho_t4)	C++20	24 / 100	545 ms	127320 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct edge { int pos,id,val; };
bool comp(edge a,edge b) { return a.id<b.id; }
const int MAXN=9e5+5;
const long long INF=1e18;
pair<int,int> val[MAXN];
vector<edge> ds[MAXN];
vector< pair<int,long long> > E[MAXN];
long long dp[MAXN];
int f(pair<int,int> a,int cnt)
{
	return lower_bound(val+1,val+cnt+1,a)-val;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,c,v;
		cin>>l>>r>>c>>v;
		ds[l].push_back({r,c,v}),ds[r].push_back({l,c,v});
		val[i*2-1]={l,r},val[i*2]={r,l};
	}
	sort(val+1,val+m*2+1);
	for(int i=1;i<=m*4;i++) E[i].push_back({m*4+val[(i-1)%(m*2)+1].second,0});
	for(int i=1;i<=n;i++)
	{
		int sz=ds[i].size(),pre=0;
		sort(ds[i].begin(),ds[i].end(),comp);
		for(int j=1;j<=sz;j++) if(j==sz||ds[i][j].id!=ds[i][j-1].id)
		{
			long long sum=0;
			for(int k=pre;k<j;k++) sum+=ds[i][k].val;
			for(int k=pre;k<j;k++) E[m*4+i].push_back({f({i,ds[i][k].pos},m*2),sum-ds[i][k].val});
			if(pre+2==j)
			{
				E[f({ds[i][j-2].pos,i},m*2)+m*2].push_back({f({i,ds[i][j-1].pos},m*2),0});
				E[f({ds[i][j-1].pos,i},m*2)+m*2].push_back({f({i,ds[i][j-2].pos},m*2),0});
			}
			pre=j;
		}
		for(auto v:ds[i])
		{
			E[m*4+i].push_back({f({i,v.pos},m*2)+m*2,v.val});
			E[f({i,v.pos},m*2)+m*2].push_back({m*4+i,-v.val});
		}
	}
	for(int i=1;i<=m*4+n;i++) dp[i]=INF;
	priority_queue< pair<long long,int>,vector< pair<long long,int> >,greater< pair<long long,int> > > pq;
	pq.push({dp[m*4+1]=0,m*4+1});
	while(!pq.empty())
	{
		long long a=pq.top().first,b=pq.top().second;
		pq.pop();
		if(dp[b]<a) continue;
		for(auto v:E[b]) if(dp[v.first]>a+v.second) pq.push({dp[v.first]=a+v.second,v.first});
	}
	if(dp[m*4+n]==INF) return cout<<-1,0;
	cout<<dp[m*4+n];
}

• Subtask 1: 0 / 34
• Subtask 2: 24 / 24
• Subtask 3: 0 / 42