Submission #493835

#	Time	Username	Problem	Language	Result	Execution time	Memory
493835		PixelCat	Robot (JOI21_ho_t4)	C++14	0 / 100	120 ms	26380 KiB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define INF (1000000000000000ll);
#define int ll
using namespace std;
using ll=long long;
using pii=pair<int,int>;

struct Edge{
	int id,col,pri;
};
vector<Edge> ed;
vector<int> adj[100010];
map<int,int> cnt[100010];
map<int,int> dist[100010];

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// nachoneko sama & miku sama bless me >/////<
	int n,m; cin>>n>>m;
	For(i,1,m){
		int a,b,c,p; cin>>a>>b>>c>>p;
		adj[a].eb(sz(ed));
		adj[b].eb(sz(ed));
		cnt[a][c]++;
		cnt[b][c]++;
		ed.push_back({a^b,c,p});
	}
	using pip=pair<int,pii>;
	priority_queue<pip,vector<pip>,greater<pip>> pq;
	pq.emplace(0,pii(0,1));
	while(!pq.empty()){
		int d=pq.top().F;
		int lcol=pq.top().S.F;
		int now=pq.top().S.S;
		pq.pop();
		if(dist[now].count(lcol)) continue;
		if(now==n){
			cout<<d<<"\n";
			exit(0);
		}
		dist[now][lcol]=d;
		for(auto &eid:adj[now]){
			auto &e=ed[eid];
			int to=e.id^now;
			if(to==1) continue;
			int count=cnt[now][e.col];
			if(!dist[to].count(e.col))
				pq.emplace(d+((count-(e.col==lcol))>1),pii(e.col,to));
		}
	}
	cout<<"-1\n";
	return 0;
}

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