oj.uz

Submission #105989

# Submission time Handle Problem Language Result Execution time Memory
105989 2019-04-16T04:35:15 Z Hideo Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 1000 ms 37240 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pii pair < int, pi >
#define vii vector < pi >

const int N = 2e5 + 7;
const int INF = 1e9 + 7;

int l[N], p[N], us[N];
int n, m, ans;

vii g[N];

void dfs (int v = 1, int c = 0){
    if (c >= us[v])
        return;
    us[v] = c;
    if (v == 2){
        ans = min(ans, c);
        return;
    }
    for (pi to : g[v])
        dfs(to.fr, c + to.sc);
}

main(){
    ans = INF;
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        us[i] = INF;
        scanf("%d%d", &l[i], &p[i]);
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            if (i != j && l[i] % p[i] == l[j] % p[i])
                g[i].pb(mk(j, abs(l[j] - l[i]) / p[i]));
    dfs();
    if (ans == INF)
        cout << -1;
    else
        cout << ans;
}

Compilation message

skyscraper.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l[i], &p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4964 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 8 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 16 ms 5120 KB Output is correct
11 Correct 951 ms 7272 KB Output is correct
12 Correct 111 ms 36984 KB Output is correct
13 Execution timed out 1064 ms 37240 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 14 ms 5120 KB Output is correct
11 Correct 869 ms 7272 KB Output is correct
12 Correct 131 ms 36988 KB Output is correct
13 Execution timed out 1070 ms 37240 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 13 ms 5120 KB Output is correct
11 Correct 904 ms 7300 KB Output is correct
12 Correct 112 ms 36984 KB Output is correct
13 Execution timed out 1071 ms 37240 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 16 ms 5120 KB Output is correct
11 Correct 811 ms 7288 KB Output is correct
12 Correct 110 ms 36984 KB Output is correct
13 Execution timed out 1051 ms 37232 KB Time limit exceeded
14 Halted 0 ms 0 KB -