oj.uz

답안 #1110003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110003 2024-11-08T12:18:13 Z HossamHero7 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 105 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 3e4 + 5;
const int SQ = 175;
vector<int> adj1[N][SQ];
vector<int> adj11[N][SQ];
vector<pair<int,int>> r_adj1[N];
vector<pair<int,int>> adj2[N];
vector<int> r_adj2[N];
void solve(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> d(m);
    for(auto &[i,p] : d) cin>>i>>p;
    vector<vector<int>> dogs(n+1);
    for(int i=0;i<m;i++) dogs[d[i].first].push_back(i);
    for(int i=0;i<n;i++){
        for(int j=1;j<SQ;j++){
            adj1[i][j].push_back(i);

            if(i+j<n) adj11[i][j].push_back(i+j) ;
            if(i-j>=0) adj11[i][j].push_back(i-j);
        }
    }
    for(int i=0;i<n;i++){
        for(auto j : dogs[i]){
            if(d[j].second < SQ) r_adj1[i].push_back({d[j].first,d[j].second});
            else r_adj2[i].push_back(j);
        }
    }
    for(int j=0;j<m;j++){
        auto [i,p] = d[j];
        if(p < SQ) continue;
        for(int k=i+p;k<n;k+=p) adj2[j].push_back({k,(k-i)/p});
        for(int k=i-p;k>=0;k-=p) adj2[j].push_back({k,(i-k)/p});
    }
    priority_queue<array<ll,4>,vector<array<ll,4>>,greater<>> q;
    vector<vector<vector<ll>>> dis(3,vector<vector<ll>>(max(n,m),vector<ll>(SQ,1e18)));
    dis[0][d[0].first][0] = 0;
    q.push({0,0,d[0].first,0});
    while(q.size()){
        auto [c,t,i,p] = q.top();     q.pop();
        assert(i < n);
        if(c > dis[t][i][p]) continue;
        if(t == 0){
            for(auto [ii,pp] : r_adj1[i]){
                if(c < dis[1][ii][pp]) {
                    //cout<<"HI"<<endl;
                    q.push({c,1,ii,pp});
                    dis[1][ii][pp] = c;
                }
            }
            for(auto j : r_adj2[i]){
                if(c < dis[2][j][0]){
                    q.push({c,2,j,0});
                    dis[2][j][0] = c;
                }
            }
        }
        else if(t == 1){

                    //if(t == 1 && i == 4 && p == 1) cout<<"WOW"<<endl;
            for(auto j : adj1[i][p]){
                if(c < dis[0][j][0]){
                    //if(i == 0 && p == 2) cout<<j<<endl;
                    q.push({c,0,j,0});
                    dis[0][j][0] = c;
                }
            }
            for(auto j : adj11[i][p]){

                    //if(t == 1 && i == 4 && p == 1) cout<<"mm"<<endl;
                if(c+1 < dis[1][j][p]){

                    //if(t == 1 && i == 4 && p == 1) cout<<j<<' '<<p<<endl;
                    q.push({c+1,1,j,p});
                    dis[1][j][p] = c+1;
                }
            }
        }
        else {
            for(auto [j,cost] : adj2[i]){
                if(c + cost < dis[0][j][0]){
                    q.push({c+cost,0,j,0});
                    dis[0][j][0] = c + cost;
                }
            }
        }
    }
    cout<<(dis[0][d[1].first][0] == 1e18 ? -1 : dis[0][d[1].first][0])<<endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto &[i,p] : d) cin>>i>>p;
      |               ^
skyscraper.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [i,p] = d[j];
      |              ^
skyscraper.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [c,t,i,p] = q.top();     q.pop();
      |              ^
skyscraper.cpp:49:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |             for(auto [ii,pp] : r_adj1[i]){
      |                      ^
skyscraper.cpp:85:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |             for(auto [j,cost] : adj2[i]){
      |                      ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 249160 KB Output is correct
2 Correct 41 ms 249160 KB Output is correct
3 Correct 42 ms 249168 KB Output is correct
4 Correct 53 ms 249164 KB Output is correct
5 Correct 55 ms 249160 KB Output is correct
6 Correct 48 ms 249148 KB Output is correct
7 Correct 58 ms 249164 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 249160 KB Output is correct
2 Correct 60 ms 249160 KB Output is correct
3 Correct 65 ms 249160 KB Output is correct
4 Correct 67 ms 249160 KB Output is correct
5 Correct 74 ms 249160 KB Output is correct
6 Correct 67 ms 249168 KB Output is correct
7 Correct 66 ms 249160 KB Output is correct
8 Correct 71 ms 249416 KB Output is correct
9 Correct 71 ms 249672 KB Output is correct
10 Correct 69 ms 252160 KB Output is correct
11 Correct 92 ms 261192 KB Output is correct
12 Correct 84 ms 261056 KB Output is correct
13 Correct 73 ms 261192 KB Output is correct
14 Correct 83 ms 261192 KB Output is correct
15 Correct 83 ms 261192 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 249068 KB Output is correct
2 Correct 66 ms 249160 KB Output is correct
3 Correct 79 ms 249160 KB Output is correct
4 Correct 86 ms 249164 KB Output is correct
5 Correct 90 ms 249160 KB Output is correct
6 Correct 82 ms 249160 KB Output is correct
7 Correct 88 ms 249244 KB Output is correct
8 Correct 87 ms 249600 KB Output is correct
9 Correct 72 ms 249672 KB Output is correct
10 Correct 78 ms 252216 KB Output is correct
11 Correct 87 ms 261192 KB Output is correct
12 Correct 80 ms 261196 KB Output is correct
13 Correct 78 ms 261192 KB Output is correct
14 Correct 93 ms 261052 KB Output is correct
15 Correct 84 ms 261196 KB Output is correct
16 Correct 82 ms 255716 KB Output is correct
17 Runtime error 88 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 249164 KB Output is correct
2 Correct 78 ms 249024 KB Output is correct
3 Correct 86 ms 249152 KB Output is correct
4 Correct 87 ms 249168 KB Output is correct
5 Correct 81 ms 249104 KB Output is correct
6 Correct 88 ms 249168 KB Output is correct
7 Correct 78 ms 249160 KB Output is correct
8 Correct 77 ms 249592 KB Output is correct
9 Correct 82 ms 249784 KB Output is correct
10 Correct 82 ms 252232 KB Output is correct
11 Correct 87 ms 261032 KB Output is correct
12 Correct 95 ms 261204 KB Output is correct
13 Correct 95 ms 261188 KB Output is correct
14 Correct 96 ms 261192 KB Output is correct
15 Correct 94 ms 261188 KB Output is correct
16 Correct 95 ms 255816 KB Output is correct
17 Runtime error 105 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 249160 KB Output is correct
2 Correct 77 ms 249160 KB Output is correct
3 Correct 83 ms 249216 KB Output is correct
4 Correct 75 ms 249160 KB Output is correct
5 Correct 79 ms 249160 KB Output is correct
6 Correct 87 ms 249160 KB Output is correct
7 Correct 79 ms 249220 KB Output is correct
8 Correct 94 ms 249416 KB Output is correct
9 Correct 82 ms 249672 KB Output is correct
10 Correct 82 ms 251984 KB Output is correct
11 Correct 92 ms 261192 KB Output is correct
12 Correct 91 ms 261188 KB Output is correct
13 Correct 97 ms 261056 KB Output is correct
14 Correct 102 ms 261192 KB Output is correct
15 Correct 97 ms 261192 KB Output is correct
16 Correct 98 ms 255816 KB Output is correct
17 Runtime error 98 ms 262144 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -