oj.uz

Submission #917635

# Submission time Handle Problem Language Result Execution time Memory
917635 2024-01-28T13:41:36 Z shenfe1 Cyberland (APIO23_cyberland) C++17
97 / 100
 1126 ms 63832 KB 
#include <bits/stdc++.h>
#include "cyberland.h"

#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#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;

int use[MAX];
vector<pii> g[MAX];

void dfs(int v,int stop){
  use[v]=1;
  if(v==stop)return;
  for(auto to:g[v]){
    if(!use[to.F])dfs(to.F,stop);
  }
}

double solve(int n,int m,int k,int h,vector<int> x,vector<int> y,vector<int> c,vector<int> arr){
  double dp[n+1][67];
  for(int i=1;i<=n;i++){
    use[i]=0;
    g[i].clear();
  }
  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";
  }
  dfs(1,h+1);
  if(!use[h+1]){
    return -1.0;
  }
  k=min(k,65);
  h++;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=k;j++)dp[i][j]=inf;
  }
  priority_queue<pair<double,pii>> q;
  for(int i=1;i<=n;i++){
    if((i==1||arr[i-1]==0)&&use[i]){
      dp[i][0]=0;
      q.push({0,{i,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(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(arr[to.F-1]==2){
        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]);
  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:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:200000000")
      | 
cyberland.cpp:8: warning: ignoring '#pragma GCC tartget' [-Wunknown-pragmas]
    8 | #pragma GCC tartget("avx2")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Correct.
2 Correct 17 ms 2904 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3420 KB Correct.
2 Correct 27 ms 3428 KB Correct.
3 Correct 20 ms 3420 KB Correct.
4 Correct 21 ms 3420 KB Correct.
5 Correct 22 ms 3420 KB Correct.
6 Correct 23 ms 8592 KB Correct.
7 Correct 28 ms 8540 KB Correct.
8 Correct 17 ms 14428 KB Correct.
9 Correct 19 ms 2888 KB Correct.
10 Correct 19 ms 2904 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3420 KB Correct.
2 Correct 22 ms 3420 KB Correct.
3 Correct 20 ms 3420 KB Correct.
4 Correct 22 ms 2904 KB Correct.
5 Correct 22 ms 2908 KB Correct.
6 Correct 7 ms 7512 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 42444 KB Correct.
2 Correct 284 ms 3860 KB Correct.
3 Correct 245 ms 3756 KB Correct.
4 Correct 265 ms 3960 KB Correct.
5 Correct 221 ms 2908 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3520 KB Correct.
2 Correct 19 ms 3420 KB Correct.
3 Correct 19 ms 3416 KB Correct.
4 Correct 23 ms 8540 KB Correct.
5 Correct 16 ms 2908 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3420 KB Correct.
2 Correct 16 ms 3416 KB Correct.
3 Correct 55 ms 47704 KB Correct.
4 Correct 15 ms 7256 KB Correct.
5 Correct 18 ms 2908 KB Correct.
6 Correct 20 ms 3420 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 4384 KB Correct.
2 Correct 39 ms 5468 KB Correct.
3 Correct 664 ms 61828 KB Correct.
4 Correct 504 ms 16428 KB Correct.
5 Correct 1126 ms 60584 KB Correct.
6 Correct 486 ms 45228 KB Correct.
7 Correct 478 ms 17756 KB Correct.
8 Correct 494 ms 5328 KB Correct.
9 Correct 213 ms 4860 KB Correct.
10 Correct 200 ms 4408 KB Correct.
11 Correct 498 ms 3796 KB Correct.
12 Correct 240 ms 4328 KB Correct.
13 Correct 258 ms 4460 KB Correct.
14 Correct 402 ms 31792 KB Correct.
15 Correct 468 ms 11092 KB Correct.
16 Correct 216 ms 4300 KB Correct.
17 Correct 279 ms 4260 KB Correct.
18 Correct 250 ms 4348 KB Correct.
19 Correct 579 ms 4460 KB Correct.
20 Correct 20 ms 3160 KB Correct.
21 Correct 17 ms 3644 KB Correct.
22 Correct 34 ms 5840 KB Correct.

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 7692 KB Correct.
2 Correct 118 ms 11740 KB Correct.
3 Incorrect 632 ms 63832 KB Wrong Answer.
4 Halted 0 ms 0 KB -