Submission #261049

#	Time	Username	Problem	Language	Result	Execution time	Memory
261049		Bill_00	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	627 ms	43140 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<unsigned int,unsigned int> >v[30000];
vector<unsigned int>loc[30000];
int b[30000],p[30000];
int vis[30000]={0};
vector<unsigned int>gg[sz][sz];
void dijkstra(unsigned int k){
	priority_queue<pair<int,unsigned int> >pq;
	pq.pp(mp(0,k));
	while(!pq.empty()){
		unsigned int now=pq.top().ss;
		int cost=-pq.top().ff;
		pq.pop();
		vis[now]++;
		if(now==1){
			flag++;
			cout << cost;
			break;
		}
		for(int i=0;i<v[now].size();i++){
			unsigned int id=v[now][i].ff;
			unsigned int add=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);
	unsigned int n,m;
	cin >> n >> m;
	for(unsigned 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(unsigned int i=0;i<m;i++){
		if(p[i]>=sz){
			for(unsigned int j=b[i];j<n;j+=p[i]){
				for(unsigned int k=0;k<loc[j].size();k++){
					if(loc[j][k]!=i){
						v[i].pb(mp(j,(j-b[i])/p[i]));
					}
				}
			}
			for(unsigned int j=b[i]-p[i];j>=0;j-=p[i]){
				for(unsigned int k=0;k<loc[j].size();k++){
					v[i].pb(mp(j,(b[i]-j)/p[i]));
				}
			}
		}
	}
	for(unsigned int i=0;i<m;i++){
		for(unsigned int j=1;j<sz;j++){
			for(unsigned 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(unsigned int)':
skyscraper.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v[now].size();i++){
               ~^~~~~~~~~~~~~~

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