oj.uz

Submission #976857

# Submission time Handle Problem Language Result Execution time Memory
976857 2024-05-07T08:03:06 Z AlperenT_ Cyberland (APIO23_cyberland) C++17
100 / 100
 2978 ms 192196 KB 
#include "cyberland.h"

#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const ll maxn = 2e5+10  , N = 1e5 +1  , maxq = 202   , inf = 1e18  , maxk = 2022  , mod =1e9+7 ;
ld dis[maxn][102] ;int mark[maxn] ,is[maxn] , is2[maxn];
vector <pair<int,ld> > G[maxn] ;
void dfs(int v){
    is[v] =1 ;
    for(auto x : G[v]){
        if(is[x.F]==1)continue ;
        dfs(x.F) ;
    }
}
int H ;
void dfs2(int v){
    is2[v] = 1 ;
    for(auto x : G[v]){
        if(is2[x.F] == 1 ||x.F==H)continue ;
        dfs2(x.F) ;
    }
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> t) {
    H = h ;
    rep(i , 0 , n-1)G[i].clear() ;
    rep(i , 0, n-1)is[i] = is2[i] =0  ;
    rep(i , 0 ,m-1){
        G[x[i]].pb({y[i] , c[i]});
        G[y[i]].pb({x[i] , c[i]}) ;
    }
    dfs(h) ;
    dfs2(0) ;
    if(is[0]== 0)return -1 ;
    k = min(k , 70);
    rep(j , 0 , n-1)rep(z , 0 , k)dis[j][z] = inf ;
    for(auto x : G[h]){
        dis[x.F][0] = x.S; 
    }
    ld ans =inf;
    rep(i , 0 , k){
        priority_queue <pair<ld,int> > pq ;
        rep(j , 0 , n-1){
            pq.push({-dis[j][i] , j}) ;
            mark[j] =0 ;
        }
        mark[h] = 1;
        while(sz(pq)){
            int v = pq.top().S ;pq.pop();
            if(mark[v] == 1)continue;
            mark[v] = 1; 
            for(auto a : G[v]){
                if(a.F == h)continue ;
                if(dis[a.F][i] > dis[v][i]+a.S){
                    dis[a.F][i] = dis[v][i] + a.S ;
                    pq.push({-dis[a.F][i] , a.F});
                }
            }        
        }
        rep(j , 0 , n-1){
            rep(z ,0 , sz(G[j])-1){
                G[j][z].S /= 2.00000000 ;
            }
        }
        rep(j , 0 , n-1){
            if(j == 0 || (t[j] == 0 && is[j] == 1 && is2[j] == 1)){
                ans = min(ans , dis[j][i]) ;
            }
        }
        rep(j , 0 , n-1){
            if(t[j]==2){
                for(auto x : G[j]){
                    dis[x.F][i+1] = min(dis[j][i] + x.S , dis[x.F][i+1]) ;
                }
            }
        }
    }
    return ans ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10844 KB Correct.
2 Correct 40 ms 10844 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 13136 KB Correct.
2 Correct 238 ms 13188 KB Correct.
3 Correct 233 ms 13144 KB Correct.
4 Correct 280 ms 13184 KB Correct.
5 Correct 239 ms 13184 KB Correct.
6 Correct 287 ms 27660 KB Correct.
7 Correct 360 ms 27336 KB Correct.
8 Correct 179 ms 45708 KB Correct.
9 Correct 161 ms 10936 KB Correct.
10 Correct 162 ms 10932 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 13648 KB Correct.
2 Correct 231 ms 13172 KB Correct.
3 Correct 216 ms 13276 KB Correct.
4 Correct 169 ms 10928 KB Correct.
5 Correct 168 ms 10932 KB Correct.
6 Correct 61 ms 24532 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 114552 KB Correct.
2 Correct 435 ms 13172 KB Correct.
3 Correct 395 ms 13096 KB Correct.
4 Correct 406 ms 13140 KB Correct.
5 Correct 266 ms 10844 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 13368 KB Correct.
2 Correct 114 ms 13396 KB Correct.
3 Correct 120 ms 13428 KB Correct.
4 Correct 192 ms 27672 KB Correct.
5 Correct 79 ms 10952 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13476 KB Correct.
2 Correct 93 ms 13408 KB Correct.
3 Correct 37 ms 18260 KB Correct.
4 Correct 110 ms 21180 KB Correct.
5 Correct 87 ms 10840 KB Correct.
6 Correct 108 ms 13360 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 13404 KB Correct.
2 Correct 38 ms 13400 KB Correct.
3 Correct 1186 ms 181528 KB Correct.
4 Correct 697 ms 50884 KB Correct.
5 Correct 1108 ms 82884 KB Correct.
6 Correct 419 ms 38972 KB Correct.
7 Correct 694 ms 52712 KB Correct.
8 Correct 532 ms 17944 KB Correct.
9 Correct 196 ms 13224 KB Correct.
10 Correct 180 ms 13396 KB Correct.
11 Correct 461 ms 13456 KB Correct.
12 Correct 239 ms 13392 KB Correct.
13 Correct 250 ms 13392 KB Correct.
14 Correct 594 ms 94444 KB Correct.
15 Correct 588 ms 34340 KB Correct.
16 Correct 198 ms 13396 KB Correct.
17 Correct 270 ms 13644 KB Correct.
18 Correct 227 ms 13276 KB Correct.
19 Correct 726 ms 13148 KB Correct.
20 Correct 12 ms 10844 KB Correct.
21 Correct 17 ms 10844 KB Correct.
22 Correct 25 ms 14172 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 13396 KB Correct.
2 Correct 81 ms 13396 KB Correct.
3 Correct 2978 ms 192196 KB Correct.
4 Correct 772 ms 25300 KB Correct.
5 Correct 2495 ms 84492 KB Correct.
6 Correct 797 ms 40364 KB Correct.
7 Correct 1121 ms 77508 KB Correct.
8 Correct 696 ms 15300 KB Correct.
9 Correct 424 ms 14156 KB Correct.
10 Correct 394 ms 14344 KB Correct.
11 Correct 357 ms 12280 KB Correct.
12 Correct 531 ms 14444 KB Correct.
13 Correct 485 ms 14284 KB Correct.
14 Correct 2320 ms 83500 KB Correct.
15 Correct 2654 ms 101000 KB Correct.
16 Correct 1131 ms 45552 KB Correct.
17 Correct 794 ms 19892 KB Correct.
18 Correct 439 ms 14476 KB Correct.
19 Correct 590 ms 14420 KB Correct.
20 Correct 504 ms 14228 KB Correct.
21 Correct 1586 ms 15268 KB Correct.
22 Correct 22 ms 11012 KB Correct.
23 Correct 35 ms 11112 KB Correct.
24 Correct 49 ms 14168 KB Correct.