Submission #666192

#	Time	Username	Problem	Language	Result	Execution time	Memory
666192		nolimiya	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	659 ms	31352 KiB

skyscraper

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//**gray sety orz**
using namespace std;
#define pi pair<int , int>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 3e4 + 5;
const long long mod = 1e9 + 7;
const int SQ = 176;
typedef long long ll;
int l,r,mid;
int n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
int darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm*SQ] , gos[maxm];
int pedaret[maxm*SQ];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st,ts;
int rp[maxm] , pr[maxm];
ll dp[maxm*SQ];
pi w[maxm];
int rw[400][400];
int dage[maxm*SQ];
map<ll,ll> mp,pm,f;
priority_queue<pi> lowq;
priority_queue<int, vector<int>, greater<int> > upq;
void bfs(int k){
	q.push(k);
	vis[k] = 1;
	while (q.size()){
		auto x = q.front();
		q.pop();
		for (auto m : g[x]){
			if (!vis[m]) vis[m] = 1 , q.push(m) , darage[m] = darage[x] + 1;
		}
	}
}
vector<int> vec;
void prep(){
	for (int i=1; i<=n; i++) vis[i] = darage[i] = 0;
}
void solve(ll x){
	for (int i=0; i<31; i++){
		if (x&(1<<i)) dp[i]++;
	}
	return ;
}
bool val(int x){
	//cout<<x<<" ";
	if (x>n/2) return 0;
	for (int i=1; i<=x; i++){
		//cout<<x<<" "<<pedaret[n-x+i]<<" "<<pedaret[i]<<endl;
		if (pedaret[n-x+i]-pedaret[i]<m) return 0;
	}
	return 1;
}
string k[maxm],t[maxm];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    int sq = sqrt(n)+1;
    for (int i=0; i<m; i++){
    	cin >>rp[i]>>pr[i];
    	if (i==0) l = rp[i];
    	if (i==1) r = rp[i];
    	g[rp[i]].push_back(pr[i]);
    }
    for (int i=0; i<n*sq; i++) pedaret[i] = mod;
    pedaret[l*sq] = 0;
	lowq.push({0,l*sq});
	while (lowq.size()){
		auto x =(lowq.top()).second;
		lowq.pop();
		if (!vis[x]){
			vis[x] = 1;
			ss = x/sq , mm = x%sq;
			if (mm==0){
				for (auto k:g[ss]){
					if (k<sq){
						mid=ss*sq+k;
						if(pedaret[mid]>pedaret[x]){
							pedaret[mid] =pedaret[x];
							lowq.push({-pedaret[mid],mid});
						}
					}
					else{
						for (int j=1; j<mod; j++){
							mid=ss-k*j;
							if (mid<0) break;
							if (pedaret[mid*sq]>pedaret[x]+j){
								pedaret[mid*sq] = pedaret[x]+j;
								lowq.push({-pedaret[mid*sq],mid*sq});
							}
						}
						for (int j = 1; j<=mod;j++){
							mid=ss+k*j;
							if (mid>=n) break;
							if (pedaret[mid*sq]>pedaret[x]+j){
								pedaret[mid*sq]=pedaret[x]+j;
								lowq.push({-pedaret[mid*sq],mid*sq});
							}
						}
					}
				}
			}
			else{
				if (pedaret[ss*sq]>pedaret[x]){
					pedaret[ss*sq] = pedaret[x] , lowq.push({-pedaret[ss*sq],ss*sq});
				}
				if(ss-mm>=0 && pedaret[(ss-mm)*sq+mm]>pedaret[x]+1){
					pedaret[(ss-mm)*sq+mm] = pedaret[x]+1;
					lowq.push({-pedaret[(ss-mm)*sq+mm],(ss-mm)*sq+mm});
				}
				if(ss+mm<n && pedaret[(ss+mm)*sq+mm]>pedaret[x]+1){
					pedaret[(ss+mm)*sq+mm] = pedaret[x]+1;
					lowq.push({-pedaret[(ss+mm)*sq+mm],(ss+mm)*sq+mm});
				}
			}
		}
	}
	if (pedaret[r*sq]==mod) return cout<<-1,0;
	cout<<pedaret[r*sq];
}

Compilation message (stderr)

skyscraper.cpp: In function 'void prep()':
skyscraper.cpp:54:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |  for (int i=1; i<=n; i++) vis[i] = darage[i] = 0;
      |                                    ~~~~~~~~~~^~~

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