Submission #553876

#	Time	Username	Problem	Language	Result	Execution time	Memory
553876		josanneo22	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1032 KiB

skyscraper

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;

void file_in(string s)
{
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
void normal()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
	if (power == 0)
		return 1;
	ll result = ex(base, power / 2);
	if (power % 2 == 1)
		return(((result * result) % mod) * base) % mod;
	else return (result * result) % mod;
}
const int maxn=30005;
int dist[maxn], B[maxn], P[maxn];
vi powers[maxn];
int n,m;
void input()
{
    
}
void solve(int s)
{
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(mp(dist[s],s));// first is distance, second is position
    pii t;
    while(!q.empty())
	{
        t=q.top(); q.pop();
        if(t.f>dist[t.s]) continue;// we only need to find minimum distance, then if already greater than, no need to continue these values;
        trav(p,powers[t.s])//powers
		{
            for(int x=1;t.s+p*x<n;++x)
			{
				int pos=t.s+p*x;
                if(dist[pos]>t.f+x)
				{
					dist[pos]=t.f+x;//keep updating minimum
                    q.push(mp(dist[pos],pos));
                    if(binary_search(all(powers[pos]),p)) break;//if there is a power there so no need to continue the other path
                }
            }
            for(int x=1;t.s-p*x>=0;++x)//duplicate but -p instead of +p
			{
				int pos=t.s-p*x;
                if(dist[pos]>t.f+x)//note that distance always increases
				{
					dist[pos]=t.f+x;
                    q.push(mp(dist[pos],pos));
                    if(binary_search(all(powers[pos]),p)) break;
                }
            }
        }
    }
}
int check()
{
	int maxi=-1;
	bool found=true;
	FOR(i,0,n)
	{
		if(dist[i]==(int)1e9)
			return -1;
		maxi=max(maxi,dist[i]);
	}
	return maxi;
}
int main()
{
	normal();
	
	cin>>n>>m;
    FOR(i,0,m)
	{
        cin>>B[i]>>P[i];
        powers[B[i]].push_back(P[i]);
    }
    FOR(i,0,n)
	{
        sort(all(powers[i]));
        powers[i].erase(unique(all(powers[i])),powers[i].end());//erase duplicates
    }
    memset(dist,(int)1e9, n);
	dist[B[0]]=0;//first move must be 0
	solve(B[0]);
	check();
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int check()':
skyscraper.cpp:98:7: warning: unused variable 'found' [-Wunused-variable]
   98 |  bool found=true;
      |       ^~~~~
skyscraper.cpp: In function 'void file_in(std::string)':
skyscraper.cpp:37:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:38:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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