Submission #493833

#	Time	Username	Problem	Language	Result	Execution time	Memory
493833		nathanlee726	Robot (JOI21_ho_t4)	C++14	34 / 100	3107 ms	682988 KiB

Main

#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define int ll
#define pii pair<int,int>
#define X first
#define Y second
#define F(n) Fi(i,n) 
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define abs(x) ((x)>0?(x):-(x))
#define pb push_back

int n,m,ind,rr[2000010],d[2000010];
vector<pair<pii,pii> >g[2000010],rg[2000010];
map<pii,int> mmp;
bool used[2000010];

void calc(int x){
	map<int,int> mp;
	for(auto pt:g[x]){
		mp[pt.X.Y]+=pt.Y.X;
	}
	F(sz(g[x])){
		g[x][i].Y.Y=mp[g[x][i].X.Y]-g[x][i].Y.X;
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	ind=n;
	F(m){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		--a,--b;
		g[a].pb({{b,c},{d,0}});
		g[b].pb({{a,c},{d,0}});
	}
	F(n)calc(i),rg[i]=g[i];
	vector<int> v;
	F(n){
		int tt=sz(g[i]);
		Fi(j,tt){
			mmp[{i,g[i][j].X.X}]=ind;
			rr[ind]=g[i][j].X.X;
			if(g[i][j].X.X==n-1)v.pb(ind);
			g[i].pb({{ind,-1},g[i][j].Y});
			g[ind]=rg[g[i][j].X.X];
			
			Fi(k,sz(g[ind])){
				if(g[ind][k].X.X!=i&&g[ind][k].X.Y==g[i][j].X.Y)g[ind][k].Y.Y-=g[i][j].Y.X;
				//if(g[ind][k].Y.Y<0)cout<<"c "<<g[ind][k].X.X<<" "<<g[ind][k].X.Y<<" "<<g[ind][k].Y.X<<" "<<g[ind][k].Y.Y<<endl;;
			}
			ind++;
		}
	}
	F(ind)d[i]=1e18;
	for(int i=n;i<ind;i++){
		for(auto pt:g[i]){
			int u=mmp[{rr[i],pt.X.X}];
			g[i].pb({{u,-1},{pt.Y}});
		}
	}
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	pq.push({0,0});
	memset(used,0,sizeof(used));
	while(!pq.empty()){
		int p=pq.top().Y,ss=pq.top().X;pq.pop();
		if(used[p])continue;
		d[p]=ss;
		//cout<<"a "<<p<<" "<<ss<<endl;
		used[p]=1;
		for(auto pt:g[p]){
			if(pt.X.X>=n){
				pq.push({ss+pt.Y.X,pt.X.X});
			}
			else{
				pq.push({ss+pt.Y.Y,pt.X.X});
			}
		}
	}
	v.pb(n-1);
	int ans=1e18;
	//for(auto pt:g[6])cout<<pt.X.X<<" "<<pt.X.Y<<" "<<pt.Y.X<<" "<<pt.Y.Y<<endl;
	//cout<<d[4]<<endl;
	//F(n)cout<<d[i]<<" ";
	//cout<<endl;
	for(int i:v)ans=min(ans,d[i]);
	cout<<(ans>1e17?-1:ans)<<endl;
	return 0;
}

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