oj.uz

Submission #78351

# Submission time Handle Problem Language Result Execution time Memory
78351 2018-10-03T17:38:48 Z xiaowuc1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 4 ms 1976 KB 
#include <bits/stdc++.h>

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

int dp[30001];
vector<int> edges[30001];
int q[30001];

int main() {
  int m, n;
  scanf("%d%d", &m, &n);
  for(int i = 0; i < m; i++) {
    dp[i] = m+1;
  }
  int ql = 0;
  int qr = 0;
  int dest = -1;
  for(int i = 0; i < n; i++) {
    int loc, jump;
    scanf("%d %d", &loc, &jump);
    edges[loc].push_back(jump);
    if(i == 0) {
      q[qr++] = loc;
      dp[loc] = 0;
    }
    else if(i == 1) {
      dest = loc;
    }
  }
  int ret = m+1;
  while(ql < qr) {
    int curr = q[ql++];
    for(int out: edges[curr]) {
      if(abs(curr-dest)%out == 0) {
        ret = min(ret, dp[curr] + abs(curr-dest) / out);
      }
      if(curr - out >= 0 && dp[curr-out] == m+1) {
        dp[curr-out] = dp[curr]+1;
        q[qr++] = curr-out;
      }
      if(dp[curr-out] == dp[curr] + 1) {
        edges[curr-out].push_back(out);
      }

      if(curr + out >= 0 && dp[curr+out] == m+1) {
        dp[curr+out] = dp[curr]+1;
        q[qr++] = curr+out;
      }
      if(dp[curr+out] == dp[curr] + 1) {
        edges[curr+out].push_back(out);
      }
    }
  }
  if(ret == m+1) ret = -1;
  printf("%d\n", ret);
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &m, &n);
   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &loc, &jump);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 3 ms 1288 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 3 ms 1416 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 3 ms 1612 KB Output is correct
4 Correct 3 ms 1672 KB Output is correct
5 Correct 3 ms 1672 KB Output is correct
6 Correct 3 ms 1748 KB Output is correct
7 Correct 3 ms 1748 KB Output is correct
8 Correct 3 ms 1748 KB Output is correct
9 Correct 3 ms 1748 KB Output is correct
10 Correct 3 ms 1752 KB Output is correct
11 Correct 3 ms 1752 KB Output is correct
12 Incorrect 3 ms 1752 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1752 KB Output is correct
2 Correct 2 ms 1804 KB Output is correct
3 Correct 2 ms 1804 KB Output is correct
4 Correct 2 ms 1804 KB Output is correct
5 Correct 3 ms 1804 KB Output is correct
6 Correct 3 ms 1804 KB Output is correct
7 Correct 2 ms 1804 KB Output is correct
8 Correct 3 ms 1804 KB Output is correct
9 Correct 3 ms 1804 KB Output is correct
10 Correct 3 ms 1804 KB Output is correct
11 Correct 3 ms 1804 KB Output is correct
12 Incorrect 3 ms 1808 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1820 KB Output is correct
2 Correct 3 ms 1824 KB Output is correct
3 Correct 3 ms 1828 KB Output is correct
4 Correct 3 ms 1832 KB Output is correct
5 Correct 3 ms 1836 KB Output is correct
6 Correct 2 ms 1840 KB Output is correct
7 Correct 3 ms 1848 KB Output is correct
8 Correct 2 ms 1848 KB Output is correct
9 Correct 3 ms 1852 KB Output is correct
10 Correct 3 ms 1856 KB Output is correct
11 Correct 3 ms 1860 KB Output is correct
12 Incorrect 3 ms 1888 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1900 KB Output is correct
2 Correct 3 ms 1904 KB Output is correct
3 Correct 3 ms 1908 KB Output is correct
4 Correct 3 ms 1912 KB Output is correct
5 Correct 3 ms 1976 KB Output is correct
6 Correct 3 ms 1976 KB Output is correct
7 Correct 3 ms 1976 KB Output is correct
8 Correct 3 ms 1976 KB Output is correct
9 Correct 3 ms 1976 KB Output is correct
10 Correct 3 ms 1976 KB Output is correct
11 Correct 4 ms 1976 KB Output is correct
12 Incorrect 4 ms 1976 KB Output isn't correct
13 Halted 0 ms 0 KB -