Submission #1237870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237870		djsksbrbf	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1096 ms	39580 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define se second
const int MAX = 3e5 + 5;
const int MOD = 1e9 + 7;
#define int ll

vector <pii> adj[MAX];
int n,m;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	vector <pii> v(m);
	for(auto &it : v)cin >> it.fi >> it.se;
	for(int i = 0 ; i < m ; i++){
		for(int j = 0 ; j < m ; j++){
			if(i== j)continue;
			ll dis = abs(v[i].fi - v[j].fi);
			if(dis % v[i].se)continue;
			
			adj[i].pb({j, dis / v[i].se});
		}
	}
	
	ll dist[m + 4];
	bool vis[m];memset(vis, 0, sizeof(vis));
	for(int i = 0 ; i <= m ; i++)dist[i] = (ll)1e18;
	dist[0] = 0;
	for(int i = 0 ; i < m ; i++){
		int t = -1;
		for(int j = 0 ; j < m ; j++){
			if(!vis[j] && (t == -1 || dist[j] < dist[t])){
				t = j;
			}
		}
		
		if(dist[t] == (ll)1e18){
			cout << -1 << endl;
			return 0;
		}
		if(t == 1){
			cout << dist[t] << endl;
			return 0;
		}
		
		vis[t] = 1;
		for(auto [nxt, we] : adj[t]){
			if(dist[nxt] > dist[t] + we){
				dist[nxt] = dist[t] + we;
			}
		}
	}
	cout << -1 << endl;
	
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/string.h:535,
                 from /usr/include/c++/11/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:48,
                 from skyscraper.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at skyscraper.cpp:33:20:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:59:33: warning: 'void* __builtin_memset(void*, int, long unsigned int)' specified size between 9223372036854775808 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   59 |   return __builtin___memset_chk (__dest, __ch, __len,
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
   60 |                                  __glibc_objsize0 (__dest));
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~

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