oj.uz

답안 #338580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338580 2020-12-23T13:02:05 Z bigDuck Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 2 ms 1004 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

ifstream fin("test_input.txt");
#define cin fin



int t, n, m, k, b[30010], p[30010];
int crd[30010];


int d[30010];
bool v[30010];
vector<pii> g[30010];
bool dog[30010];



void dijkstra(){
multiset<pii> ms;
ms.insert({d[crd[1] ], crd[1]});

while(!ms.empty()){
    auto f=*ms.begin(); ms.erase(ms.begin());
    int nod=f.sc;
    v[nod]=true;
    //cout<<nod<<" "<<d[nod]<<"y\n";
    if(nod==crd[2]){return;}

    for(auto pr:g[nod]){
        int u=pr.ft, c=pr.sc;
        if(v[u]){continue;}
        //cout<<u<<" "<<c<<"x\n";
        auto it=ms.find({d[u], u});
        if(it!=ms.end()){
            ms.erase(it);
            d[u]=min(d[u], d[nod]+c);
            ms.insert({d[u], u});
        }
        else{
                d[u]=d[nod]+c;
            ms.insert({d[u], u} );
        }
    }


}

return;
}




map<pii, int> up, down;
pii pr[30010];



void add_chain(int b, int p){

int lim=down[{b%p, p}];
int cnt=0;
for(int i=b-p; (i>=1) && ( (i>=lim) ) ; i-=p){
    if(dog[i]){g[b].pb({i, abs(i-b)/p }); cnt++; }
}
down[{b%p, p}]=max(lim, b);


if(up[{b%p, p}]==0){ up[{b%p, p }]=n+1; }
lim=up[{b%p, p}];
cnt=0;
for(int i=b+p; (i<=n) && ( (i<=lim) ) ; i+=p){
    if(dog[i]){g[b].pb({i, abs(i-b)/p });cnt++; }
}
up[{b%p, p} ]=min( lim, b);

}





int32_t main(){
INIT
cin>>n>>m;

for(int i=1; i<=n; i++){d[i]=-1; }

for(int i=1; i<=m; i++){
cin>>b[i]>>p[i]; b[i]++;
crd[i ]=b[i];
dog[b[i] ]=true;
pr[i]={b[i], p[i]};
}
sort(pr+1, pr+1+m);
for(int i=1; i<=m; i++){
    add_chain(pr[i].ft, pr[i].sc);
}
for(int i=1; i<=m; i++){
    up[{pr[i].ft%pr[i].sc, pr[i].sc} ]=0;
    down[{pr[i].ft%pr[i].sc, pr[i].sc} ]=0;
}
for(int i=m; i>=1; i--){
    add_chain(pr[i].ft, pr[i].sc);
}




d[crd[1] ]=0;
dijkstra();
cout<<d[crd[2] ];

/*for(int i=1; i<=n; i++){
    for(auto u:g[i]){
        cout<<u.ft<<" ";
    }
    cout<<"\n";
}*/



return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -