oj.uz

Submission #894899

# Submission time Handle Problem Language Result Execution time Memory
894899 2023-12-29T07:37:02 Z n0sk1ll Cyberland (APIO23_cyberland) C++17
100 / 100
 2895 ms 398060 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//const int mod=1'000'000'000;







//Note to self: Check for overflow

int k,n;
vector<vector<pii>> g(100005);
double dub[2][102][100005]; //min depth to each version of every node
bool vis[2][102][100005];

bool vist[100005]; //temporary
void dfs(int p)
{
    if (vist[p]) return;
    vist[p]=true;
    for (auto it : g[p]) dfs(it.xx);
}

void add_edge(int u, int v, int w)
{
    g[u].push_back({v,w});
}

double solve(int N, int m, int K, int H, std::vector<int> u, std::vector<int> v, std::vector<int> w, std::vector<int> arr)
{
    n=N;
    bool hyper=false;
    if (K>70) hyper=true;
    k=min(K,70);
    ff(i,0,n) g[i].clear();
    ff(stat,0,2) fff(kolko,0,k) ff(i,0,n) dub[stat][kolko][i]=0,vis[stat][kolko][i]=false;
    ff(i,0,n) vist[i]=false;
    ff(i,0,m)
    {
        if (u[i]==H) add_edge(v[i],u[i],w[i]);
        else if (v[i]==H) add_edge(u[i],v[i],w[i]);
        else add_edge(u[i],v[i],w[i]),add_edge(v[i],u[i],w[i]);
    }

    dfs(0);
    if (!vist[H]) return -1;
    vector<int> sources={0};
    ff(i,1,n) if (vist[i] && arr[i]==0) sources.push_back(i);

    #define typ pair<double,pair<int,bool>>
    priority_queue<typ,vector<typ>,greater<typ>> pq[102];
    for (auto it : sources) pq[0].push({0,{it,false}});

    if (hyper)
    {
        ff(i,1,n) if (vist[i] && arr[i]==2)
        {
            int zavoj=2*mod;
            for (auto it : g[i]) if (it.xx!=H) zavoj=min(zavoj,2*it.yy);
            pq[k].push({zavoj,{i,true}});
        }
    }

    fff(kolko,0,k) while (!pq[kolko].empty())
    {
        double d=pq[kolko].top().xx;
        int p=pq[kolko].top().yy.xx;
        bool stat=pq[kolko].top().yy.yy;
        pq[kolko].pop();
        if (vis[stat][kolko][p]) continue;
        vis[stat][kolko][p]=true;
        dub[stat][kolko][p]=d;

        for (auto it : g[p]) pq[kolko].push({d+it.yy,{it.xx,false}});
        if (arr[p]==2 && !stat) pq[kolko+1].push({d/2,{p,true}});
    }

    double ans=1e18;
    ff(stat,0,2) fff(i,0,k) if (vis[stat][i][H]) ans=min(ans,dub[stat][i][H]);
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 66520 KB Correct.
2 Correct 30 ms 66396 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 66396 KB Correct.
2 Correct 32 ms 66540 KB Correct.
3 Correct 31 ms 66392 KB Correct.
4 Correct 33 ms 66392 KB Correct.
5 Correct 32 ms 66396 KB Correct.
6 Correct 33 ms 67060 KB Correct.
7 Correct 38 ms 67144 KB Correct.
8 Correct 21 ms 68008 KB Correct.
9 Correct 31 ms 66460 KB Correct.
10 Correct 30 ms 66396 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 66568 KB Correct.
2 Correct 35 ms 66396 KB Correct.
3 Correct 32 ms 66540 KB Correct.
4 Correct 33 ms 66392 KB Correct.
5 Correct 35 ms 66392 KB Correct.
6 Correct 14 ms 67164 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 76048 KB Correct.
2 Correct 238 ms 67032 KB Correct.
3 Correct 218 ms 67048 KB Correct.
4 Correct 222 ms 66880 KB Correct.
5 Correct 112 ms 66552 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66652 KB Correct.
2 Correct 31 ms 66512 KB Correct.
3 Correct 31 ms 66840 KB Correct.
4 Correct 34 ms 67728 KB Correct.
5 Correct 26 ms 66396 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66652 KB Correct.
2 Correct 29 ms 66684 KB Correct.
3 Correct 40 ms 71504 KB Correct.
4 Correct 26 ms 67496 KB Correct.
5 Correct 29 ms 66396 KB Correct.
6 Correct 31 ms 66628 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 67836 KB Correct.
2 Correct 73 ms 68116 KB Correct.
3 Correct 564 ms 51512 KB Correct.
4 Correct 432 ms 54516 KB Correct.
5 Correct 1267 ms 127720 KB Correct.
6 Correct 1146 ms 157580 KB Correct.
7 Correct 454 ms 64192 KB Correct.
8 Correct 353 ms 62928 KB Correct.
9 Correct 321 ms 67736 KB Correct.
10 Correct 288 ms 67668 KB Correct.
11 Correct 316 ms 62816 KB Correct.
12 Correct 329 ms 67892 KB Correct.
13 Correct 385 ms 67844 KB Correct.
14 Correct 413 ms 65072 KB Correct.
15 Correct 402 ms 63664 KB Correct.
16 Correct 339 ms 67656 KB Correct.
17 Correct 376 ms 67596 KB Correct.
18 Correct 361 ms 67720 KB Correct.
19 Correct 657 ms 67092 KB Correct.
20 Correct 20 ms 66396 KB Correct.
21 Correct 27 ms 67148 KB Correct.
22 Correct 118 ms 76104 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 138920 KB Correct.
2 Correct 164 ms 139836 KB Correct.
3 Correct 309 ms 145732 KB Correct.
4 Correct 516 ms 138912 KB Correct.
5 Correct 2895 ms 267068 KB Correct.
6 Correct 2650 ms 398060 KB Correct.
7 Correct 868 ms 147384 KB Correct.
8 Correct 471 ms 138576 KB Correct.
9 Correct 726 ms 139944 KB Correct.
10 Correct 633 ms 139992 KB Correct.
11 Correct 329 ms 137524 KB Correct.
12 Correct 734 ms 140116 KB Correct.
13 Correct 805 ms 140288 KB Correct.
14 Correct 2429 ms 182940 KB Correct.
15 Correct 1420 ms 146568 KB Correct.
16 Correct 759 ms 141912 KB Correct.
17 Correct 527 ms 138864 KB Correct.
18 Correct 735 ms 139588 KB Correct.
19 Correct 843 ms 139656 KB Correct.
20 Correct 773 ms 139560 KB Correct.
21 Correct 1421 ms 139540 KB Correct.
22 Correct 37 ms 136572 KB Correct.
23 Correct 58 ms 137668 KB Correct.
24 Correct 259 ms 157408 KB Correct.