Submission #602797

#	Time	Username	Problem	Language	Result	Execution time	Memory
602797		fuad27	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	468 KiB

bridge

/*
 * Created: 2022-07-23 13:06
*/
#ifndef LOCAL
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)
 
#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
	cin.tie(0);
 
template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;
 
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;
 
 
#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
const long long inf=1e18;
void solve() {
	int n, m;
	cin >> n >> m;
	map<pll,int> mp;
	long long b[m], p[m];
	vector<pll> g[n];
	for(int i = 0;i<m;i++) {
		cin >> b[i] >> p[i];
		if(mp[mkp(b[i], p[i])])continue;
		mp[mkp(b[i],p[i])]=1;
		ll cnt=0;
		for(int j = b[i];j<n;j+=p[i]) {
			g[b[i]].push_back(mkp(j, cnt++));
		}
		cnt=0;
		for(int j = b[i];j>=0;j-=p[i]) {
			g[b[i]].push_back(mkp(j, cnt++));
		}
	}
	vc<ll> dist(n,inf);
	vc<bool> vis(n);
	dist[b[0]]=0;
	priority_queue<pll, vc<pll>, greater<pll>> pq;
	pq.push(mkp(0, b[0]));
	while(!pq.empty()) {
		int at=pq.top().second;
//		cout << at << " " << dist[at] << "\n";
		pq.pop();
		if(vis[at])continue;
		vis[at]=1;
		for(int i = 0;i<g[at].size();i++) {
			int to = g[at][i].ff, w=g[at][i].ss;
			if(dist[to]>dist[at]+w) {
				dist[to]=dist[at]+w;
				pq.push(mkp(dist[to],to));
			}
		}
	}
	if(dist[b[1]]==inf)dist[b[1]]=-1;
	cout << dist[b[1]] << "\n";
 
}
 
int main () {
	FIO;
	int t=1;
	// cin >> t;
	while(t--)
		solve();
}
 

Compilation message (stderr)

bridge.cpp: In function 'void solve()':
bridge.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i = 0;i<g[at].size();i++) {
      |                 ~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37