Submission #335620

#	Time	Username	Problem	Language	Result	Execution time	Memory
335620		Swan	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	1280 KiB

skyscraper

#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);
    for(int i = 0; i < m;i++){
        int b, p; cin >> b >> p;
        town[b].push_back(p);
        if(p > border){
            makeEdge(i, p);
        }
    }
    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){
                //cout << "opa " << i << ' ' << now << ' ' << (i % now) << endl;
                rep[now][i % now] = i;
            }
        }
    }
//    for(int i = 0; i < v[0].size();i++){
//        cout << "to " << v[0][i].first << ' ' << v[0][i].second << endl;
//    }
    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});
            //cout << "bbb " << rep[j][need] << ' ' << i << ' ' << (rep[j][need] - i)/j << ' ' << j << endl;
        }
        for(int k = 0;k < town[i].size();k++){
            int now = town[i][k];
            if(now <= border){
                //cout << "opa " << i << ' ' << now << ' ' << (i % now) << endl;
                rep[now][i % now] = i;
            }
        }
    }
    dijkstra();
    if(dist[1] == INT_MAX){
        cout << -1;
    }else{
        cout << dist[1];
    }
    return 0;
}

/*
6 1 3
8 1 2 1 5 4
*/

Compilation message (stderr)

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:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int k = 0;k < town[i].size();k++){
      |                       ~~^~~~~~~~~~~~~~~~
skyscraper.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int k = 0;k < town[i].size();k++){
      |                       ~~^~~~~~~~~~~~~~~~

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