Submission #371267

#	Time	Username	Problem	Language	Result	Execution time	Memory
371267		arnold518	Robot (JOI21_ho_t4)	C++14	100 / 100	2332 ms	297376 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;
const int MAXM = 2e6;
const ll INF = 1e18;

struct Edge
{
	int u, v, c, p, q;
};

int N, M;
Edge E[MAXN+10];
vector<Edge> adj[MAXN+10], radj[MAXN+10];
map<int, ll> MM[MAXN+10];

vector<int> VV[MAXN+10];
map<int, pii> M2[MAXN+10];
int ncnt=0;

vector<pll> adj2[MAXM+10];

ll dist[MAXM+10];

struct Queue
{
	int u; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

vector<Edge> V[MAXN+10];

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int u, v, c, p;
		scanf("%d%d%d%d", &u, &v, &c, &p);
		adj[u].push_back({u, v, c, p, i*2-1});
		adj[v].push_back({v, u, c, p, i*2});
		radj[u].push_back({v, u, c, p, i*2});
		radj[v].push_back({u, v, c, p, i*2-1});
		E[i*2-1]={u, v, c, p, i*2-1};
		E[i*2]={v, u, c, p, i*2};
		MM[u][c]+=p;
		MM[v][c]+=p;
	}
	ncnt=M*2*2;

	for(int i=1; i<=N; i++)
	{
		{
			//+in(0)
			int v=++ncnt;
			M2[i][0].first=v;
			for(auto it : radj[i])
			{
				int u=it.q;
				adj2[u].push_back({v, 0});
			}
		}
		{
			//-in(0)
			int v=++ncnt;
			M2[i][0].second=v;
			for(auto it : radj[i])
			{
				int u=it.q+2*M;
				adj2[u].push_back({v, 0});
			}
		}
		{
			for(auto it : adj[i])
			{
				V[it.c].push_back(it);
				VV[i].push_back(it.c);
			}

			sort(VV[i].begin(), VV[i].end());
			VV[i].erase(unique(VV[i].begin(), VV[i].end()), VV[i].end());

			for(auto it : VV[i])
			{
				int u1=++ncnt, u2=++ncnt;
				for(auto jt : V[it])
				{
					adj2[u1].push_back({jt.q+M*2, jt.p});
					adj2[u2].push_back({jt.q, MM[i][it]-jt.p});
				}
				M2[i][it]={u1, u2};
			}

			for(auto it : adj[i])
			{
				V[it.c].clear();
			}
		}
	}

	for(int now=1; now<=N; now++)
	{
		//printf("NOW %d\n", now);
		int u1=M2[now][0].first, u2=M2[now][0].second;
		//printf("%d %d\n", u1, u2);
		for(auto it : VV[now])
		{
			int v1=M2[now][it].first, v2=M2[now][it].second;
			//printf("%d : %d %d\n", it, v1, v2);
			adj2[u1].push_back({v1, 0});
			adj2[u2].push_back({v1, 0});
			adj2[u1].push_back({v2, 0});
			adj2[u2].push_back({v2, 0});
		}

		for(auto nxt : adj[now])
		{
			int v=M2[nxt.v][nxt.c].second;
			adj2[u2].push_back({v, 0});
			adj2[u1].push_back({v, 0});
		}
	}

	priority_queue<Queue> PQ;
	for(int i=1; i<=ncnt; i++) dist[i]=INF;

	PQ.push({M2[1][0].first, 0});
	PQ.push({M2[1][0].second, 0});
	for(auto it : VV[1])
	{
		PQ.push({M2[1][it].first, 0});
		PQ.push({M2[1][it].second, 0});
	}

	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.u]<=now.w) continue;
		//printf("%d %lld\n", now.u, now.w);
		dist[now.u]=now.w;
		for(auto nxt : adj2[now.u])
		{
			PQ.push({nxt.first, nxt.second+now.w});
		}
	}

	ll ans=INF;
	for(auto nxt : radj[N])
	{
		//printf("!%d %lld\n", nxt.q, dist[nxt.q]);
		//printf("!%d %lld\n", nxt.q+M*2, dist[nxt.q+M*2]);
		ans=min(ans, dist[nxt.q]);
		ans=min(ans, dist[nxt.q+M*2]);
	}

	if(ans==INF) ans=-1;
	printf("%lld\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:151:17: warning: narrowing conversion of 'nxt.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  151 |    PQ.push({nxt.first, nxt.second+now.w});
      |             ~~~~^~~~~
Main.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d%d%d%d", &u, &v, &c, &p);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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