Submission #253205

#	Time	Username	Problem	Language	Result	Execution time	Memory
253205		nandonathaniel	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	119 ms	117876 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=30005,INF=2e9;

int b[MAXN],p[MAXN],dist[MAXN];
vector<pii> adj[MAXN];
vector<int> doge[MAXN];
bitset<MAXN> sudah,ada[MAXN];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> b[i] >> p[i];
		doge[b[i]].push_back(p[i]);
	}
	for(int i=0;i<n;i++){
		sort(doge[i].begin(),doge[i].end());
		doge[i].erase(unique(doge[i].begin(),doge[i].end()),doge[i].end());
		reverse(doge[i].begin(),doge[i].end());
		for(auto isi : doge[i])ada[i][isi]=true;
	}
	for(int i=0;i<n;i++){
		sudah.reset();
		for(auto isi : doge[i]){
			for(int j=1;j*isi+i<n;j++){
				if(sudah[j*isi+i])continue;
				adj[i].push_back({j*isi+i,j});
				sudah[j*isi+i]=true;
				if(ada[j*isi+i][isi])break;
			}
			for(int j=1;i-j*isi>=0;j++){
				if(sudah[i-j*isi])continue;
				adj[i].push_back({i-j*isi,j});
				sudah[i-j*isi]-true;
				if(ada[i-j*isi][isi])break;
			}
		}
		dist[i]=INF;
	}
	//total edgenya jadi N*sqrt(N) kayanya
	priority_queue<pii,vector<pii>,greater<pii> > PQ;
	dist[b[1]]=0;
	PQ.push({0,b[1]});
	while(!PQ.empty()){
		pii now=PQ.top();
		PQ.pop();
		if(dist[now.second]<now.first)continue;
		for(auto nxt : adj[now.second]){
			if(dist[now.second]+nxt.second<dist[nxt.first]){
				dist[nxt.first]=dist[now.second]+nxt.second;
				PQ.push({dist[nxt.first],nxt.first});
			}
		}
	}
	if(dist[b[2]]==INF)dist[b[2]]=-1;
	cout << dist[b[2]] << '\n';
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:19: warning: value computed is not used [-Wunused-value]
     sudah[i-j*isi]-true;

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