oj.uz

Submission #335623

# Submission time Handle Problem Language Result Execution time Memory
335623 2020-12-13T10:54:33 Z Swan Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 2 ms 1280 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("balance.in","r",stdin)
#define OUTP freopen("balance.out","w",stdout)
using namespace std;


const int maxn = 30001;
int n, m;
int border;
int rep[200][200];
vector<vector<pair<int, int> > > v;
vector<int> town[maxn];
int dist[maxn];

void cleanRep(){
    for(int i = 0; i < 200;i++){
        for(int j = 0; j < 200;j++){
            rep[i][j] = -1;
        }
    }
}

void makeEdge(int start, int p){
    int r = start + p;
    int cnt = 1;
    while(r < n){
        v[start].push_back({cnt, r});
        cnt++;
        r+=p;
    }
    int l = start - p;
    cnt = 1;
    while(l >= 0){
        v[start].push_back({cnt, l});
        cnt++;
        l-=p;
    }
}

void dijkstra(){
    priority_queue<pair<int,int> > q;
    for(int i = 0; i < n;i++){
        dist[i] = INT_MAX;
    }
    dist[0] = 0;
    q.push({0, 0});
    while(q.size()){
        int now = q.top().second;
        int nowDist = -q.top().first;
        q.pop();
        if(dist[now] < nowDist)continue;
        for(int i = 0; i < v[now].size();i++){
            int to = v[now][i].second;
            int toDist = dist[now] + v[now][i].first;
            //cout << "darove " << now << ' ' << to << ' ' << toDist << endl;
            if(dist[to] <= toDist)continue;
            dist[to] = toDist;
            q.push({-toDist, to});
        }
    }
}

main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    border = sqrt(n);
    cleanRep();
    v.resize(n + 2);
    int need = INT_MAX;
    for(int i = 0; i < m;i++){
        int b, p; cin >> b >> p;
        town[b].push_back(p);
        if(p > border){
            makeEdge(i, p);
        }
        if(i == 1){
            need = b;
        }
    }
    cleanRep();
    for(int i = 0; i<n;i++){
        for(int j = 1; j <= border;j++){
            int need = i % j;
            if(rep[j][need] == -1)continue;
            v[rep[j][need]].push_back({(i - rep[j][need])/j,i});
            //cout << "aaa " << rep[j][need] << ' ' << i << ' ' << (i - rep[j][need])/j << ' ' << j << endl;
        }
        for(int k = 0;k < town[i].size();k++){
            int now = town[i][k];
            if(now <= border){
                rep[now][i % now] = i;
            }
        }
    }
    cleanRep();
    for(int i = n - 1; i>=0;i--){
        for(int j = 1; j <= border;j++){
            int need = i % j;
            if(rep[j][need] == -1)continue;
            v[rep[j][need]].push_back({(rep[j][need] - i)/j,i});
        }
        for(int k = 0;k < town[i].size();k++){
            int now = town[i][k];
            if(now <= border){
                rep[now][i % now] = i;
            }
        }
    }
    dijkstra();
    if(need == INT_MAX){
        cout << -1;
    }
    else if(dist[need] == INT_MAX){
        cout << -1;
    }else{
        cout << dist[need];
    }
    return 0;
}

/*
10 3
0 5
5 2
7 6
*/

Compilation message

skyscraper.cpp: In function 'void dijkstra()':
skyscraper.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 0; i < v[now].size();i++){
      |                        ~~^~~~~~~~~~~~~~~
skyscraper.cpp: At global scope:
skyscraper.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main(){
      |      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int k = 0;k < town[i].size();k++){
      |                       ~~^~~~~~~~~~~~~~~~
skyscraper.cpp:103:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int k = 0;k < town[i].size();k++){
      |                       ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Incorrect 1 ms 1260 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 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1280 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Incorrect 1 ms 1260 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 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Incorrect 1 ms 1260 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 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1260 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 1 ms 1260 KB Output is correct
8 Incorrect 1 ms 1260 KB Output isn't correct
9 Halted 0 ms 0 KB -