Submission #1104218

#TimeUsernameProblemLanguageResultExecution timeMemory
11042188pete8Airplane (NOI23_airplane)C++17
100 / 100
313 ms43164 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<cassert> #include<unordered_map> #include <queue> #include <cstdint> #include<cstring> #include<limits.h> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> #include<bitset> using namespace std; #define ll long long #define f first #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-lopps") #define int long long using namespace std; const int mod=998244353,mxn=5e5+5,inf=1e18,minf=-1e18,lg=20; //#undef int int n,k,m,q; void setIO(string name){ ios_base::sync_with_stdio(0); cin.tie(0); freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } vector<int>adj[mxn+10]; int val[mxn+10]; vector<int>solve(int st){ vector<int>dist(n+1,inf),last(n+1,-1); priority_queue<pii,vector<pii>,greater<pii>>pq; pq.push({0,st}); dist[st]=0; while(!pq.empty()){ int cur=pq.top().s,cost=pq.top().f; pq.pop(); if(dist[cur]!=cost||last[cur]==cost)continue; last[cur]=cost; for(auto i:adj[cur])if(dist[i]>max(val[i],dist[cur]+1)){ dist[i]=max(val[i],dist[cur]+1); pq.push({dist[i],i}); } } return dist; } int32_t main(){ fastio cin>>n>>m; for(int i=1;i<=n;i++)cin>>val[i]; for(int i=0;i<m;i++){ int a,b;cin>>a>>b; adj[a].pb(b); adj[b].pb(a); } vector<int>dist1=solve(1),dist2=solve(n); int ans=inf; for(int i=1;i<=n;i++){ ans=min(ans,max(dist1[i],dist2[i])*2); for(auto j:adj[i])ans=min(ans,max(dist1[i],dist2[j])*2+1); } cout<<ans; } /* */

Compilation message (stderr)

Main.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
Main.cpp:45:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 | vector<int>solve(int st){
      |                        ^
Main.cpp:62:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   62 | int32_t main(){
      |              ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...