oj.uz

Submission #397341

# Submission time Handle Problem Language Result Execution time Memory
397341 2021-05-01T22:49:14 Z Bitmasking Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 226 ms 131112 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define f(i,a,b) for( ll i = a; i < b ; i++ )
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ones(ini) (ll) __builtin_popcountll(x)
#define cuantos(a,x) count(all(a),x)
#define fs first
#define sc second
#define pb push_back
#define po pop_back
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ller ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define watch(x) cout << (#x) << " is " << (x) <<"\n"
#define test ll deftestcases;cin>>deftestcases;while(deftestcases--)
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> ii;
typedef vector<ll>  vi;
typedef vector<ii> vii;
template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
const ll inf = 2e18;
const ll mod = 1e9+7;   
const ll MAX = 1e5+10;

vii adj[MAX];
set<ll> aux[MAX];
ll dis[MAX];
void dijkstra(ll root,ll n){
    f(i,0,n+4){
        dis[i] = -1;
    }
    priority_queue<ii,vii,greater<ii>> pq;
    dis[root] = 0;
    pq.push({dis[root],root});
    while(sz(pq)){
        ll u = pq.top().sc;
        ll d = pq.top().fs;
        pq.pop();
        if(dis[u]!=d) continue;
        for(auto v : adj[u]){
            ll to = v.fs,w = v.sc;
            if(dis[to]==-1 || dis[u]+w<dis[to]){
                dis[to] = dis[u]+w;
                pq.push({dis[to],to});
            }
        }
    }
}

void ida(ll u,ll n){
    for(auto pod : aux[u]){
            ll to = 0,mul=1;
            while(to<=n){
                to = pod*mul+u;
                if(to>=n) break;
                adj[u].pb({to,mul});
                if(aux[to].count(pod)) break;
                mul++;  
            }
    }
}
void vuelta(ll u){
    for(auto pod : aux[u]){
        ll to = 0,mul=1;
        while(to>=0){
            to = u-pod*mul;
            if(to<0) break;
            adj[u].pb({to,mul});
            if(aux[to].count(pod)) break;
            mul++;    
        }
    }
}
int main(){
    fastio;
    ll n,m;cin>>n>>m;
    ll ini=0,meta=0;
    f(i,0,m){
        ll b,p;cin>>b>>p;
        if(!i) ini = b;
        if(i==1) {meta = b;continue;}
        aux[b].insert(p);
    }
    f(u,0,n){
        ida(u,n);
        vuelta(u);
    }
    dijkstra(ini,n);
    cout<<dis[meta]<<"\n";
    return 0; 
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 6 ms 7356 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7268 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7324 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7272 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 6 ms 7832 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7500 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 5 ms 7500 KB Output is correct
23 Correct 5 ms 7500 KB Output is correct
24 Correct 6 ms 7756 KB Output is correct
25 Correct 6 ms 7628 KB Output is correct
26 Correct 5 ms 7500 KB Output is correct
27 Correct 6 ms 7484 KB Output is correct
28 Correct 7 ms 7908 KB Output is correct
29 Correct 8 ms 8780 KB Output is correct
30 Correct 6 ms 7884 KB Output is correct
31 Correct 6 ms 8216 KB Output is correct
32 Correct 6 ms 7908 KB Output is correct
33 Correct 11 ms 10184 KB Output is correct
34 Correct 10 ms 10184 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 6 ms 7248 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 5 ms 7376 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 6 ms 7376 KB Output is correct
17 Correct 6 ms 7756 KB Output is correct
18 Correct 5 ms 7500 KB Output is correct
19 Correct 6 ms 7500 KB Output is correct
20 Correct 6 ms 7580 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 5 ms 7500 KB Output is correct
23 Correct 6 ms 7500 KB Output is correct
24 Correct 6 ms 7756 KB Output is correct
25 Correct 6 ms 7628 KB Output is correct
26 Correct 5 ms 7500 KB Output is correct
27 Correct 5 ms 7476 KB Output is correct
28 Correct 5 ms 7884 KB Output is correct
29 Correct 8 ms 8780 KB Output is correct
30 Correct 6 ms 7884 KB Output is correct
31 Correct 6 ms 8268 KB Output is correct
32 Correct 6 ms 8012 KB Output is correct
33 Correct 11 ms 10212 KB Output is correct
34 Correct 11 ms 10184 KB Output is correct
35 Correct 26 ms 10572 KB Output is correct
36 Correct 8 ms 7888 KB Output is correct
37 Correct 29 ms 12316 KB Output is correct
38 Correct 29 ms 12228 KB Output is correct
39 Correct 29 ms 12288 KB Output is correct
40 Correct 29 ms 12244 KB Output is correct
41 Correct 29 ms 12284 KB Output is correct
42 Correct 9 ms 7500 KB Output is correct
43 Correct 9 ms 7500 KB Output is correct
44 Correct 9 ms 7500 KB Output is correct
45 Correct 30 ms 17192 KB Output is correct
46 Correct 32 ms 17168 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 4 ms 7312 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7480 KB Output is correct
17 Correct 6 ms 7756 KB Output is correct
18 Correct 6 ms 7500 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7500 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 5 ms 7500 KB Output is correct
23 Correct 5 ms 7500 KB Output is correct
24 Correct 6 ms 7784 KB Output is correct
25 Correct 6 ms 7628 KB Output is correct
26 Correct 5 ms 7600 KB Output is correct
27 Correct 5 ms 7500 KB Output is correct
28 Correct 6 ms 7892 KB Output is correct
29 Correct 8 ms 8800 KB Output is correct
30 Correct 7 ms 7944 KB Output is correct
31 Correct 7 ms 8216 KB Output is correct
32 Correct 6 ms 8012 KB Output is correct
33 Correct 11 ms 10184 KB Output is correct
34 Correct 11 ms 10184 KB Output is correct
35 Correct 22 ms 10572 KB Output is correct
36 Correct 7 ms 7884 KB Output is correct
37 Correct 27 ms 12364 KB Output is correct
38 Correct 28 ms 12280 KB Output is correct
39 Correct 29 ms 12312 KB Output is correct
40 Correct 32 ms 12256 KB Output is correct
41 Correct 35 ms 12220 KB Output is correct
42 Correct 9 ms 7500 KB Output is correct
43 Correct 9 ms 7500 KB Output is correct
44 Correct 9 ms 7572 KB Output is correct
45 Correct 31 ms 17204 KB Output is correct
46 Correct 31 ms 17160 KB Output is correct
47 Correct 58 ms 26048 KB Output is correct
48 Correct 28 ms 12948 KB Output is correct
49 Correct 19 ms 11192 KB Output is correct
50 Correct 16 ms 10984 KB Output is correct
51 Correct 48 ms 16208 KB Output is correct
52 Correct 49 ms 17260 KB Output is correct
53 Correct 19 ms 10436 KB Output is correct
54 Correct 7 ms 8144 KB Output is correct
55 Correct 8 ms 8908 KB Output is correct
56 Correct 17 ms 10520 KB Output is correct
57 Correct 43 ms 24760 KB Output is correct
58 Correct 14 ms 9164 KB Output is correct
59 Correct 14 ms 10436 KB Output is correct
60 Correct 18 ms 11332 KB Output is correct
61 Correct 16 ms 10312 KB Output is correct
62 Correct 31 ms 18516 KB Output is correct
63 Correct 89 ms 50904 KB Output is correct
64 Correct 102 ms 58684 KB Output is correct
65 Correct 127 ms 77480 KB Output is correct
66 Correct 225 ms 130992 KB Output is correct
67 Correct 226 ms 131112 KB Output is correct