oj.uz

Submission #922151

# Submission time Handle Problem Language Result Execution time Memory
922151 2024-02-05T07:10:43 Z tosivanmak Cyberland (APIO23_cyberland) C++17
100 / 100
 2720 ms 78880 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double eps=1e-10;
 
 ll n;
struct thing{
   long double val; ll node;
   bool operator<(const thing& t)const{
       return (val)>t.val;
   }
   thing(long double _val, ll _node){
       val=_val,node=_node;
   }
};
bool vis[100005][72];
 double dist[100005][72];
priority_queue<thing>q;
vector<int>oarr;
vector<int>hv;
vector<pair<int,double> >adj[100005];
void Dstra(ll ban, ll lvl){
    for(int i=0;i<n;i++){
        if(i!=ban&&dist[i][lvl]!=1e18){
           q.push(thing(dist[i][lvl],i));
        }
    }
   while(!q.empty()){
       thing t=q.top();
       q.pop();
    //    cout<<t.val<<'\n';
       ll cur=t.node;
       if(vis[cur][lvl]){
           continue;
       }
       vis[cur][lvl]=1;
       for(pair<int,double>& u: adj[cur]){
           if(u.first==ban){
               continue;
           }
           if(oarr[u.first]==2&&lvl+1<=70){
                   if(((dist[cur][lvl]+u.second)/2.0-eps)<dist[u.first][lvl+1]&&!vis[u.first][lvl+1]){
                     dist[u.first][lvl+1]=(dist[cur][lvl]+u.second)/2.0;
                    //  q.push(thing(dist[u.first][cur.second+1],{u.first,cur.second+1}));
                   }
               }
           if(!vis[u.first][lvl]){
               if(dist[cur][lvl]+u.second<dist[u.first][lvl]){
                   dist[u.first][lvl]=dist[cur][lvl]+u.second;
                   q.push(thing(dist[u.first][lvl],u.first));
               }
           }
           
       }
   }
}
bool visi[100005];
void dfs(ll s, ll ban){
    visi[s]=1;
    for(pair<int,double>& u: adj[s]){
        if(!visi[u.first]&&ban!=u.first){
            dfs(u.first,ban);
        }
    }
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
   oarr=arr;
   int m=M,k=K,h=H;n=N;
   k=min(k,70);
   for(int i=0;i<n;i++){
       for(int j=0;j<72;j++){
           dist[i][j]=1e18;
           vis[i][j]=0;
       }
       visi[i]=0;
   }
   for(int i=0;i<m;i++){
       adj[x[i]].push_back({y[i],(double)c[i]});
       adj[y[i]].push_back({x[i],(double)c[i]});
   }
   dfs(0,h);
   for(int i=0;i<n;i++){
       if(visi[i]&&arr[i]==0){
           hv.push_back(i);
       }
   }
   for(auto& u: hv){
       for(int i=0;i<72;i++){
           dist[u][i]=0;
       }
   }
   dist[0][0]=0;
   for(int i=0;i<=70;i++){
       Dstra(h,i);
   }
//    return -1;
   hv.clear();oarr.clear();
  double ans=1e18;
   for(auto& u: adj[h]){
       for(int i=0;i<=k;i++){
            //    cout<<dist[u.first][i]<<" "<<u.second<<'\n';
               ans=min(ans,dist[u.first][i]+u.second);
       }
   }
//   for(int i=0;i<n;i++){
//       for(int j=0;j<=3;j++){
//           cout<<dist[i][j]<<" ";
//       }
//       cout<<'\n';
//   }
   for(int i=0;i<n;i++){
       visi[i]=0;
       adj[i].clear();
       for(int j=0;j<72;j++){
           vis[i][j]=0;
       }
   }
   if(1e18-ans<=eps){
       return -1;
   }
   return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7000 KB Correct.
2 Correct 26 ms 4916 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5712 KB Correct.
2 Correct 28 ms 7772 KB Correct.
3 Correct 27 ms 4456 KB Correct.
4 Correct 28 ms 4444 KB Correct.
5 Correct 29 ms 4616 KB Correct.
6 Correct 27 ms 12124 KB Correct.
7 Correct 33 ms 11040 KB Correct.
8 Correct 22 ms 17440 KB Correct.
9 Correct 26 ms 7512 KB Correct.
10 Correct 29 ms 3828 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 4604 KB Correct.
2 Correct 313 ms 7744 KB Correct.
3 Correct 297 ms 4404 KB Correct.
4 Correct 199 ms 7508 KB Correct.
5 Correct 199 ms 7400 KB Correct.
6 Correct 104 ms 11864 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 50636 KB Correct.
2 Correct 185 ms 7764 KB Correct.
3 Correct 157 ms 7832 KB Correct.
4 Correct 171 ms 7760 KB Correct.
5 Correct 112 ms 7504 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7764 KB Correct.
2 Correct 29 ms 8280 KB Correct.
3 Correct 26 ms 7772 KB Correct.
4 Correct 25 ms 13268 KB Correct.
5 Correct 30 ms 7516 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 7952 KB Correct.
2 Correct 138 ms 8020 KB Correct.
3 Correct 61 ms 62548 KB Correct.
4 Correct 155 ms 10588 KB Correct.
5 Correct 112 ms 7504 KB Correct.
6 Correct 161 ms 8380 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 7956 KB Correct.
2 Correct 29 ms 7004 KB Correct.
3 Correct 2720 ms 77460 KB Correct.
4 Correct 910 ms 25560 KB Correct.
5 Correct 945 ms 36916 KB Correct.
6 Correct 330 ms 18892 KB Correct.
7 Correct 865 ms 25388 KB Correct.
8 Correct 584 ms 11192 KB Correct.
9 Correct 144 ms 7764 KB Correct.
10 Correct 148 ms 7840 KB Correct.
11 Correct 483 ms 9040 KB Correct.
12 Correct 160 ms 7772 KB Correct.
13 Correct 160 ms 7944 KB Correct.
14 Correct 1249 ms 41856 KB Correct.
15 Correct 771 ms 18036 KB Correct.
16 Correct 151 ms 7780 KB Correct.
17 Correct 184 ms 7996 KB Correct.
18 Correct 179 ms 8212 KB Correct.
19 Correct 565 ms 8656 KB Correct.
20 Correct 11 ms 6744 KB Correct.
21 Correct 13 ms 6860 KB Correct.
22 Correct 26 ms 7516 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 7948 KB Correct.
2 Correct 29 ms 7004 KB Correct.
3 Correct 268 ms 78880 KB Correct.
4 Correct 794 ms 11540 KB Correct.
5 Correct 984 ms 36880 KB Correct.
6 Correct 348 ms 18904 KB Correct.
7 Correct 1095 ms 33828 KB Correct.
8 Correct 499 ms 8984 KB Correct.
9 Correct 147 ms 7764 KB Correct.
10 Correct 148 ms 7924 KB Correct.
11 Correct 194 ms 7824 KB Correct.
12 Correct 161 ms 8012 KB Correct.
13 Correct 163 ms 7768 KB Correct.
14 Correct 1247 ms 37704 KB Correct.
15 Correct 1230 ms 44420 KB Correct.
16 Correct 896 ms 21056 KB Correct.
17 Correct 592 ms 11188 KB Correct.
18 Correct 154 ms 8604 KB Correct.
19 Correct 191 ms 8020 KB Correct.
20 Correct 175 ms 7932 KB Correct.
21 Correct 561 ms 8868 KB Correct.
22 Correct 12 ms 6748 KB Correct.
23 Correct 13 ms 6748 KB Correct.
24 Correct 30 ms 7516 KB Correct.