Submission #863748

#TimeUsernameProblemLanguageResultExecution timeMemory
863748Huseyn123Dreaming (IOI13_dreaming)C++17
100 / 100
54 ms15060 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define MAX 100001 #define INF INT_MAX #define MOD 1000000007 #define mp make_pair #define mt make_tuple #define pb push_back #define ins insert #define ff first #define ss second #define gett(x,m) get<m>(x) #define all(a) a.begin(),a.end() #define lb(a,b) lower_bound(all(a),b) #define ub(a,b) upper_bound(all(a),b) #define sortv(a) sort(all(a)) #define sorta(a,sz) sort(a,a+sz) #define inputar(a,b){\ for(int i=0;i<b;i++){\ cin >> a[i];\ }\ } #define inputvec(a,b){\ for(int i=0;i<b;i++){\ ll num;\ cin >> num;\ a.pb(num);\ }\ } #define outputar(a,b){\ for(int i=0;i<b;i++){\ cout << a[i] << " ";\ }\ cout << "\n";\ } #define outputvec(a){\ for(auto x:a){\ cout << x << " ";\ }\ cout << "\n";\ } #define reset(a,n,v){\ for(int i=0;i<n;i++){\ a[i]=v;\ }\ } using namespace std; typedef long long ll; typedef unsigned long long ull; typedef tuple<ll,ll,ll> tll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef double db; typedef long double ldb; inline void USACO(string filename){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } vector<vector<pii>> g; vector<int> used; vector<int> e; vector<int> dist; vector<int> pre; void dfs(int v,int prev){ e.pb(v); used[v]=1; for(auto x:g[v]){ if(x.ff==prev){ continue; } dist[x.ff]=dist[v]+x.ss; dfs(x.ff,v); } } void dfs1(int v,int prev){ pre[v]=prev; for(auto x:g[v]){ if(x.ff==prev){ continue; } dist[x.ff]=dist[v]+x.ss; dfs1(x.ff,v); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int res; g.resize(N); dist.resize(N,0); used.resize(N,0); pre.resize(N,0); for(int i=0;i<M;i++){ g[A[i]].pb(mp(B[i],T[i])); g[B[i]].pb(mp(A[i],T[i])); } int maxd=0; vector<int> c; for(int i=0;i<N;i++){ if(used[i]==0){ e.clear(); dfs(i,-1); int maxd1,ind; maxd1=-1; for(auto x:e){ if(dist[x]>maxd1){ maxd1=dist[x]; ind=x; } dist[x]=0; } dfs1(ind,-1); maxd1=-1; int ind1; for(auto x:e){ if(dist[x]>maxd1){ maxd1=dist[x]; ind1=x; } } maxd=max(maxd,maxd1); int ind2=ind1; int h=dist[ind1]-dist[ind]; while(ind1!=ind){ h=min(h,max(dist[ind2]-dist[ind1],dist[ind1]-dist[ind])); ind1=pre[ind1]; } c.pb(h); } } sortv(c); reverse(all(c)); if(c.size()==1){ res=c[0]; } else{ res=c[0]+c[1]+L; } if(c.size()>2){ res=max(res,c[1]+c[2]+2*L); } res=max(maxd,res); return res; } /* int main(){ int n,m,k; cin >> n >> m >> k; int A[m],B[m],T[m]; for(int i=0;i<m;i++){ cin >> A[i] >> B[i] >> T[i]; } cout << travelTime(n,m,k,A,B,T); } */

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:121:19: warning: 'ind1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |    int h=dist[ind1]-dist[ind];
      |                   ^
dreaming.cpp:122:14: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |    while(ind1!=ind){
      |          ~~~~^~~~~
#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...