Submission #1228086

#TimeUsernameProblemLanguageResultExecution timeMemory
1228086Nika533Cyberland (APIO23_cyberland)C++17
44 / 100
3092 ms135108 KiB
#pragma GCC diagnostic warning "-std=c++11" #include <bits/stdc++.h> #include "cyberland.h" #define pb push_back #define f first #define s second #define MOD 1000000007 #define flush fflush(stdout) #define all(x) (x).begin(),(x).end() #define allr(x) (x).rbegin(), (x).rend() #define pii pair<int,int> using namespace std; const int N=1e5+5; int n,m,k,val[N],fix[N],fix2[N]; pair<double,int> dist[N][105]; vector<pair<int,int>> g[N]; void dfs2(int x) { if (fix2[x]) return; fix2[x]=1; for (auto AA:g[x]) { dfs2(AA.f); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) { n=N; m=M; k=K; for (int i=1; i<=n; i++) { g[i].clear(); fix[i]=0; fix2[i]=0; for (int j=0; j<=k; j++) { dist[i][j]={1e18,0}; } } for (int i=1; i<=n; i++) { val[i]=arr[i-1]; } for (int i=0; i<m; i++) { g[x[i]+1].pb({y[i]+1,c[i]}); g[y[i]+1].pb({x[i]+1,c[i]}); // cout<<x[i]+1<<" "<<y[i]+1<<endl; } val[1]=0; fix2[H+1]=2; dfs2(1); priority_queue<pair<long long,int>> q; for (int i=1; i<=n; i++) { if (val[i]==0 && fix2[i]==1) { dist[i][0].f=0; q.push({0,i}); } } for (int j=0; j<=k; j++) { while (!q.empty()) { int v=q.top().s; q.pop(); if (fix[v]) continue; fix[v]=1; for (auto AA:g[v]) { int u=AA.f; long long w=AA.s; if (dist[u][j].f>dist[v][j].f+w) { dist[u][j].f=dist[v][j].f+w; dist[u][j].s=1; q.push({-dist[u][j].f,u}); } } } for (int i=1; i<=n; i++) { if (val[i]!=2) { dist[i][j+1]=dist[i][j]; dist[i][j+1].s=0; } else if (i!=H+1 && dist[i][j].s==1) { dist[i][j+1].f=dist[i][j].f/2; dist[i][j+1].s=0; } q.push({-dist[i][j+1].f,i}); fix[i]=0; } } double ans=1e18,big=1e17; ans=dist[H+1][k].f; if (dist[H+1][k].f>=big) return -1; return ans; }

Compilation message (stderr)

cyberland.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...