oj.uz

Submission #484288

# Submission time Handle Problem Language Result Execution time Memory
484288 2021-11-02T21:46:47 Z MilosMilutinovic Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 1 ms 1016 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=30100;
int n,m,b[N],p[N],d[N];
VI qs[N];
int main() {
	scanf("%d%d",&n,&m);
	rep(i,0,m) {
		scanf("%d%d",b+i,p+i);
		qs[b[i]].pb(p[i]);
	}
	rep(i,0,n) d[i]=(1<<29);
	priority_queue<pair<int,int>> q;
	q.push(mp(0,b[0])); d[0]=0;
	while (SZ(q)) {
		auto x=q.top(); q.pop();
		if (d[x.se]<-x.fi) continue;
		for (int j:qs[x.se]) {
			for (int u=x.se-j;u>=0;u-=j) {
				if (d[u]>d[x.se]+(x.se-u)/j) {
					d[u]=d[x.se]+(x.se-u)/j;
					q.push(mp(-d[u],u));
				}
			}
			for (int u=x.se+j;u<n;u+=j) {
				if (d[u]>d[x.se]+(u-x.se)/j) {
					d[u]=d[x.se]+(u-x.se)/j;
					q.push(mp(-d[u],u));
				}
			}
		}
	}
	if (d[b[1]]==(1<<29)) printf("-1");
	else printf("%d",d[b[1]]);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d",b+i,p+i);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 1008 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1012 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1008 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 1016 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 1012 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Incorrect 1 ms 972 KB Output isn't correct
9 Halted 0 ms 0 KB -