oj.uz

Submission #917612

# Submission time Handle Problem Language Result Execution time Memory
917612 2024-01-28T13:19:06 Z shenfe1 Cyberland (APIO23_cyberland) C++17
97 / 100
 3000 ms 157168 KB 
#include <bits/stdc++.h>
#include "cyberland.h"
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("03")
#pragma GCC tartget("avx2")
 
using namespace std;
 
#define F first
#define S second
#define pb push_back
#define pii pair<int,int>
 
const int MAX=1e5+15;
const double inf=1e18;
 
double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){
  vector<pii> g[n+1];
  double dp[n+1][67];
  for(int i=0;i<m;i++){
    x[i]++;
    y[i]++;
    g[x[i]].pb({y[i],c[i]});
    g[y[i]].pb({x[i],c[i]});
    // cout<<x[i]<<" "<<y[i]<<" "<<c[i]<<"\n";
  }
  k=min(k,66);
  h++;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=k;j++)dp[i][j]=inf;
  }
  dp[1][0]=0;
  priority_queue<pair<double,pii>> q;
  q.push({0,{1,0}});
  while(!q.empty()){
    int v=q.top().S.F,c=q.top().S.S;
    if(dp[v][c]<-q.top().F||v==h){
      q.pop();
      continue;
    }
    q.pop();
    // cout<<v<<" "<<c<<" "<<dp[v][c]<<"\n";
    for(auto to:g[v]){
      if(arr[to.F-1]==0){
        if(dp[to.F][c]>0){
          dp[to.F][c]=0;
          q.push({-dp[to.F][c],{to.F,c}});
        }
      }
      else if(arr[to.F-1]==1){
        if(dp[v][c]+to.S<dp[to.F][c]){
          dp[to.F][c]=dp[v][c]+to.S;
          q.push({-dp[to.F][c],{to.F,c}});
        }
      }
      else{
        if(dp[v][c]+to.S<dp[to.F][c]){
          dp[to.F][c]=dp[v][c]+to.S;
          q.push({-dp[to.F][c],{to.F,c}});
        }
        if(c+1<=k&&(dp[v][c]+to.S)/2<dp[to.F][c+1]){
          dp[to.F][c+1]=(dp[v][c]+to.S)/2;
          q.push({-dp[to.F][c+1],{to.F,c+1}});
        }
      }
    }
  }
  double ans=inf;
  for(int i=0;i<=k;i++)ans=min(ans,dp[h][i]);
  if(ans==inf)return -1.0;
  return ans;
}
 
// int main(){
//   ios_base::sync_with_stdio(0);
//   cin.tie(0);
//   cout.tie(0);
//   int t;
//   cin>>t;
//   cout.precision(10);
//   while(t--){
//     int n,m,k,h;
//     cin>>n>>m>>k>>h;
//     vector<int> arr(n);
//     for(int i=0;i<n;i++)cin>>arr[i];
//     vector<int> x(m),y(m),c(m);
//     for(int i=0;i<m;i++)cin>>x[i]>>y[i]>>c[i];
//     cout<<fixed<<solve(n,m,k,h,x,y,c,arr)<<"\n";
//   }
// }

Compilation message

cyberland.cpp:6: warning: ignoring '#pragma GCC tartget' [-Wunknown-pragmas]
    6 | #pragma GCC tartget("avx2")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 856 KB Correct.
2 Correct 18 ms 604 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1116 KB Correct.
2 Correct 24 ms 860 KB Correct.
3 Correct 22 ms 1096 KB Correct.
4 Correct 25 ms 1116 KB Correct.
5 Correct 24 ms 1100 KB Correct.
6 Correct 28 ms 6332 KB Correct.
7 Correct 28 ms 6236 KB Correct.
8 Correct 17 ms 12380 KB Correct.
9 Correct 20 ms 544 KB Correct.
10 Correct 20 ms 556 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 856 KB Correct.
2 Correct 24 ms 860 KB Correct.
3 Correct 23 ms 1112 KB Correct.
4 Correct 22 ms 348 KB Correct.
5 Correct 22 ms 348 KB Correct.
6 Correct 7 ms 5212 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 36016 KB Correct.
2 Correct 525 ms 1100 KB Correct.
3 Correct 455 ms 1368 KB Correct.
4 Correct 485 ms 860 KB Correct.
5 Correct 414 ms 596 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1112 KB Correct.
2 Correct 24 ms 860 KB Correct.
3 Correct 22 ms 1112 KB Correct.
4 Correct 24 ms 6236 KB Correct.
5 Correct 18 ms 344 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Correct.
2 Correct 20 ms 860 KB Correct.
3 Correct 60 ms 46900 KB Correct.
4 Correct 16 ms 4704 KB Correct.
5 Correct 21 ms 552 KB Correct.
6 Correct 21 ms 1116 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 2424 KB Correct.
2 Correct 55 ms 2836 KB Correct.
3 Correct 1633 ms 59888 KB Correct.
4 Correct 1255 ms 13972 KB Correct.
5 Correct 1154 ms 59056 KB Correct.
6 Correct 401 ms 28052 KB Correct.
7 Correct 1224 ms 15480 KB Correct.
8 Correct 1193 ms 2860 KB Correct.
9 Correct 378 ms 2056 KB Correct.
10 Correct 393 ms 2472 KB Correct.
11 Correct 1170 ms 1620 KB Correct.
12 Correct 408 ms 2076 KB Correct.
13 Correct 403 ms 2680 KB Correct.
14 Correct 977 ms 30524 KB Correct.
15 Correct 1351 ms 8612 KB Correct.
16 Correct 389 ms 1876 KB Correct.
17 Correct 484 ms 1920 KB Correct.
18 Correct 476 ms 2000 KB Correct.
19 Correct 1422 ms 2468 KB Correct.
20 Correct 27 ms 600 KB Correct.
21 Correct 31 ms 1504 KB Correct.
22 Correct 33 ms 3536 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1687 ms 8284 KB Correct.
2 Correct 176 ms 5264 KB Correct.
3 Correct 645 ms 61524 KB Correct.
4 Correct 2880 ms 5964 KB Correct.
5 Execution timed out 3030 ms 157168 KB Time limit exceeded
6 Halted 0 ms 0 KB -