oj.uz

Submission #443756

# Submission time Handle Problem Language Result Execution time Memory
443756 2021-07-12T03:03:54 Z Killer2501 Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 988 ms 35516 KB 
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define task "slingshot"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long

using namespace std;
const ll mod =  1e9;
const ll N = 1e5+5;
const int base = 300;
ll n, m, t, ans, k, a[N], b[N], c[N], tong,  cnt, q, d[N], P[N][21], h[N], lab[N], dp[N][200];
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

struct point
{
    ll x, y;
}p[N];
vector<ll> dx, dy;
vector<ll> adj[N], kq, gr[N];

string s[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
ll A(ll u, ll v)
{
    if(u > v)return 0;
    return b[v] * c[v-u] % mod;
}
ll findp(ll u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
    u = findp(u);
    v = findp(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}
void add(ll id)
{
    for(; id <= n;id += id & -id)++d[id];
}
ll get(ll id)
{
    ll total = 0;
    for(; id; id -= id & -id)total += d[id];
    return total;
}
ll lwr(ll x)
{
    return lower_bound(kq.begin(), kq.end(), x) - kq.begin() + 1;
}
void dfs(ll u, ll p)
{
    a[u] = ++m;
    for(int i = 1; i <= 20; i ++)P[u][i] = P[P[u][i-1]][i-1];
    for(ll v : adj[u])
    {
        if(v == p)continue;
        h[v] = h[u] + 1;
        P[v][0] = u;
        dfs(v, u);
    }
}
bool cmp(const ll& x, const ll& y)
{
    return a[x] < a[y];
}
ll lca(ll u, ll v)
{
    if(h[u] < h[v])swap(u, v);
    ll log = log2(h[u]);
    for(int i = log; i >= 0; i --)if(h[u] >= h[v] + (1<<i))u = P[u][i];
    if(u == v)return u;
    for(int i = log; i >= 0; i --)
    {
        if(P[u][i] && P[u][i] != P[v][i])
        {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[u][0];
}
void cal(ll u, ll p)
{
    for(ll v : adj[u])
    {
        if(v == p)continue;
        cal(v, u);
        c[u] += c[v];
    }
    if(c[u])hop(u, P[u][0]);
}
void sol()
{
    cin >> m >> n;
    k = 180;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i] >> b[i];
        adj[a[i]].pb(b[i]);
    }
    for(int i = 0; i < m; i ++)for(int j = 0; j <= k; j ++)dp[i][j] = mod;
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    dp[a[0]][0] = 0;
    pq.push({0, {a[0], 0}});
    while(!pq.empty())
    {
        pii u = pq.top();
        pq.pop();
        if(u.fi != dp[u.se.fi][u.se.se])continue;
        if(!u.se.se)
        {
            for(ll v : adj[u.se.fi])
            {
                if(v < k)
                {
                    if(dp[u.se.fi][v] > u.fi)
                    {
                        dp[u.se.fi][v] = u.fi;
                        pq.push({u.fi, {u.se.fi, v}});
                    }
                }
                else
                {
                    for(int j = u.se.fi - v, c = 1; j >= 0; j -= v, c++)
                    {
                        if(dp[j][0] > u.fi + c)
                        {
                            dp[j][0] = u.fi + c;
                            pq.push({dp[j][0], {j, 0}});
                        }
                    }
                    for(int j = u.se.fi + v, c = 1; j < m; j += v, c ++)
                    {
                        if(dp[j][0] > u.fi + c)
                        {
                            dp[j][0] = u.fi + c;
                            pq.push({dp[j][0], {j, 0}});
                        }
                    }
                }
            }
        }
        else
        {
            if(u.se.fi + u.se.se < m && dp[u.se.fi+u.se.se][u.se.se] > u.fi+1)
            {
                dp[u.se.fi+u.se.se][u.se.se] = u.fi+1;
                pq.push({u.fi+1, {u.se.fi+u.se.se, u.se.se}});
            }
            if(u.se.fi - u.se.se >= 0 && dp[u.se.fi-u.se.se][u.se.se] > u.fi+1)
            {
                dp[u.se.fi-u.se.se][u.se.se] = u.fi+1;
                pq.push({u.fi+1, {u.se.fi-u.se.se, u.se.se}});
            }
            if(dp[u.se.fi][0] > u.fi)
            {
                dp[u.se.fi][0] = u.fi;
                pq.push({u.fi, {u.se.fi, 0}});
            }
        }
    }
    ans = dp[a[1]][0];
    if(ans == mod)ans = -1;
    cout << ans;
}
int main()
{
    if(fopen(task".in", "r")){
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:187:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:188:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 5 ms 8108 KB Output is correct
7 Correct 5 ms 8088 KB Output is correct
8 Correct 5 ms 8140 KB Output is correct
9 Correct 5 ms 8140 KB Output is correct
10 Correct 5 ms 8140 KB Output is correct
11 Correct 6 ms 8268 KB Output is correct
12 Correct 5 ms 8268 KB Output is correct
13 Correct 6 ms 8268 KB Output is correct
14 Correct 7 ms 8268 KB Output is correct
15 Correct 8 ms 8268 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 5 ms 8080 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 5 ms 8140 KB Output is correct
9 Correct 5 ms 8140 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct
11 Correct 7 ms 8268 KB Output is correct
12 Correct 6 ms 8268 KB Output is correct
13 Correct 6 ms 8268 KB Output is correct
14 Correct 8 ms 8268 KB Output is correct
15 Correct 7 ms 8268 KB Output is correct
16 Correct 5 ms 8268 KB Output is correct
17 Correct 8 ms 8704 KB Output is correct
18 Correct 6 ms 9548 KB Output is correct
19 Correct 6 ms 9676 KB Output is correct
20 Correct 7 ms 9804 KB Output is correct
21 Correct 6 ms 8396 KB Output is correct
22 Correct 6 ms 9548 KB Output is correct
23 Correct 7 ms 9420 KB Output is correct
24 Correct 8 ms 9644 KB Output is correct
25 Correct 7 ms 9676 KB Output is correct
26 Correct 7 ms 9676 KB Output is correct
27 Correct 7 ms 9676 KB Output is correct
28 Correct 8 ms 9804 KB Output is correct
29 Correct 14 ms 9744 KB Output is correct
30 Correct 8 ms 9676 KB Output is correct
31 Correct 10 ms 9676 KB Output is correct
32 Correct 11 ms 9720 KB Output is correct
33 Correct 23 ms 9816 KB Output is correct
34 Correct 22 ms 9748 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 5 ms 8140 KB Output is correct
7 Correct 5 ms 8140 KB Output is correct
8 Correct 5 ms 8140 KB Output is correct
9 Correct 5 ms 8140 KB Output is correct
10 Correct 6 ms 8140 KB Output is correct
11 Correct 6 ms 8268 KB Output is correct
12 Correct 7 ms 8268 KB Output is correct
13 Correct 6 ms 8280 KB Output is correct
14 Correct 8 ms 8296 KB Output is correct
15 Correct 8 ms 8268 KB Output is correct
16 Correct 6 ms 8344 KB Output is correct
17 Correct 10 ms 8780 KB Output is correct
18 Correct 8 ms 9548 KB Output is correct
19 Correct 7 ms 9632 KB Output is correct
20 Correct 7 ms 9804 KB Output is correct
21 Correct 6 ms 8396 KB Output is correct
22 Correct 7 ms 9548 KB Output is correct
23 Correct 7 ms 9420 KB Output is correct
24 Correct 8 ms 9652 KB Output is correct
25 Correct 7 ms 9676 KB Output is correct
26 Correct 8 ms 9676 KB Output is correct
27 Correct 8 ms 9676 KB Output is correct
28 Correct 8 ms 9804 KB Output is correct
29 Correct 15 ms 9772 KB Output is correct
30 Correct 8 ms 9676 KB Output is correct
31 Correct 10 ms 9720 KB Output is correct
32 Correct 9 ms 9760 KB Output is correct
33 Correct 21 ms 9800 KB Output is correct
34 Correct 22 ms 9816 KB Output is correct
35 Correct 21 ms 9864 KB Output is correct
36 Correct 9 ms 9036 KB Output is correct
37 Correct 29 ms 10088 KB Output is correct
38 Correct 28 ms 10316 KB Output is correct
39 Correct 27 ms 10316 KB Output is correct
40 Correct 28 ms 10248 KB Output is correct
41 Correct 31 ms 10492 KB Output is correct
42 Correct 12 ms 10168 KB Output is correct
43 Correct 12 ms 10188 KB Output is correct
44 Correct 12 ms 10096 KB Output is correct
45 Correct 69 ms 10672 KB Output is correct
46 Correct 72 ms 10636 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8144 KB Output is correct
2 Correct 5 ms 8140 KB Output is correct
3 Correct 5 ms 8168 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 5 ms 8140 KB Output is correct
6 Correct 5 ms 8112 KB Output is correct
7 Correct 6 ms 8140 KB Output is correct
8 Correct 5 ms 8140 KB Output is correct
9 Correct 5 ms 8140 KB Output is correct
10 Correct 5 ms 8140 KB Output is correct
11 Correct 8 ms 8268 KB Output is correct
12 Correct 6 ms 8268 KB Output is correct
13 Correct 6 ms 8268 KB Output is correct
14 Correct 8 ms 8268 KB Output is correct
15 Correct 7 ms 8268 KB Output is correct
16 Correct 6 ms 8268 KB Output is correct
17 Correct 8 ms 8812 KB Output is correct
18 Correct 6 ms 9548 KB Output is correct
19 Correct 6 ms 9676 KB Output is correct
20 Correct 7 ms 9804 KB Output is correct
21 Correct 6 ms 8396 KB Output is correct
22 Correct 6 ms 9548 KB Output is correct
23 Correct 7 ms 9420 KB Output is correct
24 Correct 8 ms 9676 KB Output is correct
25 Correct 7 ms 9676 KB Output is correct
26 Correct 7 ms 9676 KB Output is correct
27 Correct 9 ms 9676 KB Output is correct
28 Correct 8 ms 9804 KB Output is correct
29 Correct 14 ms 9676 KB Output is correct
30 Correct 8 ms 9688 KB Output is correct
31 Correct 11 ms 9764 KB Output is correct
32 Correct 9 ms 9712 KB Output is correct
33 Correct 22 ms 9804 KB Output is correct
34 Correct 21 ms 9812 KB Output is correct
35 Correct 22 ms 9764 KB Output is correct
36 Correct 10 ms 9104 KB Output is correct
37 Correct 29 ms 10192 KB Output is correct
38 Correct 28 ms 10364 KB Output is correct
39 Correct 36 ms 10244 KB Output is correct
40 Correct 29 ms 10316 KB Output is correct
41 Correct 29 ms 10240 KB Output is correct
42 Correct 14 ms 10092 KB Output is correct
43 Correct 12 ms 10188 KB Output is correct
44 Correct 12 ms 10092 KB Output is correct
45 Correct 69 ms 10660 KB Output is correct
46 Correct 71 ms 10636 KB Output is correct
47 Correct 107 ms 18828 KB Output is correct
48 Correct 24 ms 26920 KB Output is correct
49 Correct 24 ms 28652 KB Output is correct
50 Correct 23 ms 30376 KB Output is correct
51 Correct 73 ms 32956 KB Output is correct
52 Correct 76 ms 32972 KB Output is correct
53 Correct 35 ms 32412 KB Output is correct
54 Correct 20 ms 31556 KB Output is correct
55 Correct 21 ms 31548 KB Output is correct
56 Correct 31 ms 32812 KB Output is correct
57 Correct 102 ms 31744 KB Output is correct
58 Correct 28 ms 32064 KB Output is correct
59 Correct 31 ms 32072 KB Output is correct
60 Correct 37 ms 32224 KB Output is correct
61 Correct 32 ms 32076 KB Output is correct
62 Correct 56 ms 32744 KB Output is correct
63 Correct 77 ms 33756 KB Output is correct
64 Correct 103 ms 33760 KB Output is correct
65 Correct 366 ms 33780 KB Output is correct
66 Correct 988 ms 35212 KB Output is correct
67 Correct 978 ms 35516 KB Output is correct