Submission #530453

#TimeUsernameProblemLanguageResultExecution timeMemory
530453__VariattoDreaming (IOI13_dreaming)C++17
0 / 100
47 ms14220 KiB
#include <bits/stdc++.h> #include"dreaming.h" using namespace std; #define pb push_back #define fi first #define se second #define ll long long const int MAX=1e5+10, MAXV=1e9+10; int n, m, l, odl[MAX][2]; vector<pair<int,int>>g[MAX]; pair<int,int>maxi; bool odw[MAX]; void dfso(int v, int oj, int x, int nr){ odl[v][nr]=x; odw[v]=true; maxi=max(maxi, {x, v}); for(auto s: g[v]) if(s.fi!=oj) dfso(s.fi, v, x+s.se, nr); } pair<int,int>mini; void dfs(int v, int oj){ mini=min(mini, {max(odl[v][0], odl[v][1]), v}); for(auto s: g[v]) if(s.fi!=oj) dfs(s.fi,v); } int travelTime(int N, int M, int L, int a[], int b[], int t[]){ n=N, m=M, l=L; for(int i=0; i<m; i++) g[a[i]].pb({b[i], t[i]}), g[b[i]].pb({a[i], t[i]}); int ls1=-1, ls2=-1, lmid=-1, dl=0, lmids1=0, lmids2=0; for(int i=0; i<n; i++){ if(odw[i]) continue; maxi={0,0}; dfso(i, i, 0, 0); int s1=maxi.se; maxi={0,0}; dfso(s1, s1, 0, 0); int s2=maxi.se; maxi={0,0}; dfso(s2, s2, 0, 1); mini={MAXV,0}; dfs(i, i); int mid=mini.se; int mids1=odl[mid][0], mids2=odl[mid][1]; if(ls1==-1){ ls1=s1, ls2=s2, lmid=mid, dl=odl[s2][0], lmids1=mids1, lmids2=mids2; continue; } if(dl<max(mids1, mids2)+max(lmids1, lmids2)+l){ dl=max(mids1, mids2)+max(lmids1, lmids2)+l; int nmid, ns1, ns2, nmids1, nmids2; if(mids1>mids2 && lmids1>lmids2){ ns1=s1, ns2=ls1; if(max(mids1, lmids1+l)<max(lmids1, mids1+l)) nmid=mid, nmids1=mids1, nmids2=lmids1+l; else nmid=lmid, nmids1=mids1+l, nmids2=lmids1; } if(mids1>mids2 && lmids2>lmids1){ ns1=s1, ns2=ls2; if(max(mids1, lmids2+l)<max(lmids2, mids1+l)) nmid=mid, nmids1=mids1, nmids2=lmids2+l; else nmid=lmid, nmids1=mids1+l, nmids2=lmids2; } if(mids2>mids1 && lmids1>lmids2){ ns1=s2, ns2=ls1; if(max(mids2, lmids1+l)<max(lmids1, mids2+l)) nmid=mid, nmids1=mids2, nmids2=lmids1+l; else nmid=lmid, nmids1=mids2+l, nmids2=lmids1; } if(mids2>mids1 && lmids2>lmids1){ ns1=s2, ns2=ls2; if(max(mids2, lmids2+l)<max(lmids2, mids2+l)) nmid=mid, nmids1=mids2, nmids2=lmids2+l; else nmid=lmid, nmids1=mids2+l, nmids2=lmids2; } lmid=nmid, lmids1=nmids1, lmids2=nmids2, ls1=ns1, ls2=ns2; } //cout<<ls1<<" "<<ls2<<" "<<dl<<" "<<lmids1<<" "<<lmids2<<"\n"; } return dl; } /*int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int N, M, L, CA, CB, CT; vector<int>A, B, T; cin>>N>>M>>L; for(int i=1; i<=M; i++){ cin>>CA>>CB>>CT; A.pb(CA), B.pb(CB), T.pb(CT); } cout<<travelTime(N, M, L, A, B, T)<<"\n"; } */

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:28: warning: 'lmids2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |             if(mids1>mids2 && lmids2>lmids1){
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~
dreaming.cpp:62:28: warning: 'lmids1' may be used uninitialized in this function [-Wmaybe-uninitialized]
dreaming.cpp:48:9: warning: 'ls1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |         if(ls1==-1){
      |         ^~
#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...