Submission #300369

#	Time	Username	Problem	Language	Result	Execution time	Memory
300369		Bill_00	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	700 ms	51336 KiB

skyscraper

#include <bits/stdc++.h>
typedef long long ll;
#define fr(i,c,d) for(ll i=c;i<=d;i++)
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pp push
using namespace std;
//int h[200001],p[200001];
//int sum[100001];
//pair<ll,ll>p[100001];
//pair<ll,ll>p1[100001];
//string s;
const int sz=173;
string str(string x,int l,int r){
	string h;
	for(int i=l;i<=r;i++){
		h+=x[i];
	}
	return h;
}
int flag=0;
vector<pair<int,int> >v[30000];
vector<int>loc[30000];
int b[30000],p[30000];
int vis[30000]={0};
vector<int>gg[sz][sz];
void dijkstra(int k){
	priority_queue<pair<int,ll> >pq;
	pq.pp(mp(0,k));
	while(!pq.empty()){
		int now=pq.top().ss;
		ll cost=-pq.top().ff;
		pq.pop();
		vis[now]++;
		if(now==1){
			flag++;
			cout << cost;
			break;
		}
		for(int i=0;i<v[now].size();i++){
			int id=v[now][i].ff;
			ll add=(ll)v[now][i].ss;
			if(vis[id]==0){
				pq.pp(mp(-(cost+add),id));
			}
		}
		while(!pq.empty() && vis[pq.top().ss]==1) pq.pop();
	}
}
int main(){
	//int color[200001];
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		cin >> b[i] >> p[i];
		loc[b[i]].pb(i);
		if(p[i]<sz){
			gg[p[i]][b[i]%p[i]].pb(i);
		}
	}
	for(int i=0;i<m;i++){
		if(p[i]>=sz){
			for(int j=b[i]+p[i];j<n;j+=p[i]){
				for(int k=0;k<loc[j].size();k++){
					v[i].pb(mp(loc[j][k],(j-b[i])/p[i]));
				}
			}
			for(int j=b[i]-p[i];j>=0;j-=p[i]){
				for(int k=0;k<loc[j].size();k++){
					v[i].pb(mp(loc[j][k],(b[i]-j)/p[i]));
				}
			}
		}
	}
	for(int i=0;i<m;i++){
		for(int j=1;j<sz;j++){
			for(int k=0;k<gg[j][b[i]%j].size();k++){
				if(gg[j][b[i]%j][k]!=i) v[gg[j][b[i]%j][k]].pb(mp(i,abs(b[i]-b[gg[j][b[i]%j][k]])/j));
			}	
		}
	}
	dijkstra(0);
	if(flag==0) cout << -1;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra(int)':
skyscraper.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=0;i<v[now].size();i++){
      |               ~^~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int k=0;k<loc[j].size();k++){
      |                 ~^~~~~~~~~~~~~~
skyscraper.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int k=0;k<loc[j].size();k++){
      |                 ~^~~~~~~~~~~~~~
skyscraper.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for(int k=0;k<gg[j][b[i]%j].size();k++){
      |                ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43