Submission #1120917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120917		RSAMSD	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	3 ms	1872 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
int t = 0;
int const f = 3e4 + 10;
long long mod = 1e9 + 7;//998244353;
long long dp1[f];
long long dp2[f];
long long par[f];
long long a[f];
long long adj[f];
long long mmn =0;
pair<long long, long long> edges[f];
long long prefix[f];
vector<pair<int,int>>g[f];
vector<int>gr[f];
struct node {
	long long val = 0;
	long long lazy = 0;
};
struct trpel {
	long long v, u, bank = 0;
};
node segtree[f * 8];
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("std.in");
	fout.open("std.out");
}
void build(int v , int l , int r){
	if(r==l){
		segtree[v].val = 1e9;
		return;
	}
	int mid = (r+l)/2;
	build(2*v+1,mid+1,r);
	build(2*v,l,mid);
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
void upd(int v, int l, int r , int pos, int val){
	if(r==l&&r==pos){
		segtree[v].val = val;
		return;
	}
	int mid = (r+l)/2;
	if(pos>mid){
		upd(2*v+1,mid+1,r,pos,val);
	}
	else{
		upd(2*v,l,mid,pos,val);
	}
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
long long q(int v, int tl , int tr , int l ,int r){
	if(tl>r||tr<l)return 0;
	if(tr<=r&&tl>=l){
		return segtree[v].val;
	}
	int mid = (tr+tl)/2;
	return max(q(2*v,tl,mid,l,r),q(2*v+1,mid+1,tr,l,r));
}
// void merge(int a , int b, int n, int id){
	// if(g[a].size()>g[b].size()){
		// swap(a,b);
	// }
	// for(int u:g[a]){
		// if(u<n&&!B[u]&&par[u+1]==b){
			// upd(1,1,n,u,id);
			// B[u]=1;
		// }
		// if(u>1&&!B[u-1]&&par[u-1]==b){
			// upd(1,1,n,u-1,id);
			// B[u-1] =1;
		// }
		// g[b].push_back(u);
		// par[u] = b;
	// }
// }
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
long long tw = powmod(2, mod - 2, mod);
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	//cin >> t;
	t = 1;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long double dec = 0;
		bool c = 1;
		bool allrows =0;
		bool allculms =0;
		priority_queue<pair<long long, long long>> qq;
		multiset<long long> mul;
		queue<long long> pp;
		map<pair<long long, pair<long long, long long>>, long long> conv;
		vector<long long> vec;
		cin >> n >> m;
		for(int i =0;i<m;i++){
			cin>>r>>l;
			g[r].push_back({l,r});
			a[i] = r;
		}
		pp.push(a[0]);
		dp2[a[0]] = 0;
		dp2[a[1]] = 1e18;
		while(dp2[a[1]]==1e18&&!pp.empty()){
			d = pp.front();
			pp.pop();
			for(auto u:g[d]){
				if(u.second!=d-u.first&&d-u.first>0){
					g[d-u.first].push_back({u.first,d});
					pp.push(d-u.first);
					dp2[d-u.first] = dp2[d]+1;
				}
				if(u.second!=d+u.first&&d+u.first<n){
					pp.push(d+u.first);
					g[d+u.first].push_back({u.first,d});
					dp2[d+u.first] = dp2[d]+1;
				}
			}
			g[d].clear();
		}
		if(dp2[a[1]]==1e18){
			cout<<-1;
		}
		else{
			cout<<dp2[a[1]];
		}
	}
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:104:16: warning: unused variable 'mx' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                ^~
skyscraper.cpp:104:38: warning: unused variable 'k' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                      ^
skyscraper.cpp:104:45: warning: unused variable 'k2' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                             ^~
skyscraper.cpp:104:60: warning: unused variable 'rr' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                            ^~
skyscraper.cpp:104:75: warning: unused variable 'll' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                           ^~
skyscraper.cpp:104:83: warning: unused variable 'lll' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                   ^~~
skyscraper.cpp:104:92: warning: unused variable 'rrr' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                            ^~~
skyscraper.cpp:104:101: warning: unused variable 'inf' [-Wunused-variable]
  104 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                                     ^~~
skyscraper.cpp:107:8: warning: unused variable 's2' [-Wunused-variable]
  107 |   char s2;
      |        ^~
skyscraper.cpp:108:15: warning: unused variable 'dec' [-Wunused-variable]
  108 |   long double dec = 0;
      |               ^~~
skyscraper.cpp:109:8: warning: unused variable 'c' [-Wunused-variable]
  109 |   bool c = 1;
      |        ^
skyscraper.cpp:110:8: warning: unused variable 'allrows' [-Wunused-variable]
  110 |   bool allrows =0;
      |        ^~~~~~~
skyscraper.cpp:111:8: warning: unused variable 'allculms' [-Wunused-variable]
  111 |   bool allculms =0;
      |        ^~~~~~~~

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