Submission #51048

#TimeUsernameProblemLanguageResultExecution timeMemory
51048mirbek01Rail (IOI14_rail)C++17
30 / 100
106 ms34652 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; const int N = 5e3 + 2; int n, dist[N][N], cur; bool cmp(int a, int b){ return dist[cur][a] < dist[cur][b]; } void findLocation(int N, int first, int location[], int stype[]){ location[0] = first; stype[0] = 1; if(N == 1) return ; vector <int> l, r, v; n = N; int in = 1; for(int i = 1; i < n; i ++){ dist[0][i] = dist[i][0] = getDistance(0, i); if(dist[0][i] < dist[0][in]) in = i; } location[in] = first + dist[0][in]; stype[in] = 2; for(int i = 1; i < n; i ++){ if(in == i) continue; dist[in][i] = dist[i][in] = getDistance(in, i); } for(int i = 1; i < n; i ++){ if(i == in) continue; if(dist[in][i] < dist[0][in]){ location[i] = location[in] - dist[in][i]; stype[i] = 1; } else { if(dist[0][in] + dist[in][i] == dist[0][i]) l.push_back(i); else r.push_back(i); } } sort(r.begin(), r.end(), cmp); for(int i : r){ bool ok = 1; if(!v.empty()){ int d = getDistance(i, v.back()); int pos = location[v.back()] - d; if(first < pos){ int lo; for(int j = v.size() - 1; j >= 0; j --){ if(location[v[j]] > pos){ lo = j; break; } } int x = d - (location[v.back()] - location[v[lo]]); if(dist[0][i] == dist[0][v[lo]] + x){ location[i] = location[v[lo]] - x; stype[i] = 1; ok = 0; } } } if(ok){ location[i] = first + dist[0][i]; stype[i] = 2; v.push_back(i); } } v.clear(); cur = in; sort(l.begin(), l.end(), cmp); for(int i : l){ bool ok = 1; if(!v.empty()){ int d = getDistance(i, v.back()); int pos = location[v.back()] + d; if(pos < location[in]){ int lo; for(int j = v.size() - 1; j >= 0; j --){ if(location[v[j]] < pos){ lo = j; break; } } int x = d - (location[v[lo]] - location[v.back()]); if(dist[in][i] == dist[in][v[lo]] + x){ location[i] = location[v[lo]] + x; stype[i] = 2; ok = 0; } } } if(ok){ location[i] = location[in] - dist[in][i]; stype[i] = 1; v.push_back(i); } } }

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:80:29: warning: 'lo' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int lo;
                             ^~
rail.cpp:50:29: warning: 'lo' may be used uninitialized in this function [-Wmaybe-uninitialized]
                         int lo;
                             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...