Submission #576191

#TimeUsernameProblemLanguageResultExecution timeMemory
576191elazarkorenRail (IOI14_rail)C++17
56 / 100
141 ms600 KiB
#include "rail.h" #include <bits/stdc++.h> #define x first #define y second #define all(v) v.begin(), v.end() #define chkmin(a, b) a = min(a, b) #define chkmax(a, b) a = max(a, b) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vii; const int MAX_N = 5005; int dist0[MAX_N], dist1[MAX_N], dist2[MAX_N]; void findLocation(int n, int first, int location[], int stype[]) { int closest = 1; for (int i = 1; i < n; i++) { dist0[i] = getDistance(0, i); if (dist0[i] < dist0[closest]) closest = i; } location[0] = first, stype[0] = 1; location[closest] = dist0[closest] + first, stype[closest] = 2; vi ind_l, ind_r; dist1[0] = dist0[closest]; bitset<MAX_N> visited; visited[0] = visited[closest] = true; for (int i = 1; i < n; i++) { if (i == closest) continue; dist1[i] = getDistance(closest, i); if (dist0[i] != dist0[closest] + dist1[i]) { ind_r.push_back(i); } else if (dist1[i] > dist1[0]) { ind_l.push_back(i); } else { location[i] = location[closest] - dist1[i]; stype[i] = 1; visited[i] = true; } } if (!ind_r.empty()) { sort(all(ind_r), [&] (int i, int j) { return dist0[i] < dist0[j]; }); // int last = ind_r[0]; // location[last] = first + dist0[last]; // stype[last] = 2; // visited[last] = true; // vi v = {last}; for (int i : ind_r) { if (visited[i]) continue; stype[i] = 2; location[i] = dist0[i] + first; // last = i; visited[i] = true; for (int j : ind_r) { if (visited[j]) continue; int d = getDistance(i, j); if (dist0[j] == dist0[i] + d){ location[j] = location[i] - d; stype[j] = 1; visited[j] = true; } } // int d = getDistance(last, i); // int x1 = location[last] - d; // int j; // for (int k : v) { // if (location[k] > x1) { // j = k; // break; // } // } // if (getDistance(j, i) + dist0[j] != dist0[i]) { // stype[i] = 2; // location[i] = dist0[i] + first; // last = i; // v.push_back(i); // } else { // stype[i] = 1; // location[i] = first + 2 * dist0[j] - dist0[i]; // } } } if (!ind_l.empty()) { sort(all(ind_l), [&] (int i, int j) { return dist1[i] < dist1[j]; }); // int last = ind_l[0]; // location[last] = location[closest] - dist1[last]; // stype[last] = 1; // visited[last] = true; // vi v = {last}; for (int i : ind_l) { if (visited[i]) continue; stype[i] = 1; location[i] = location[closest] - dist1[i]; // last = i; visited[i] = true; for (int j : ind_l) { if (visited[j]) continue; int d = getDistance(i, j); if (dist1[j] == dist1[i] + d) { location[j] = location[i] + d; stype[j] = 2; visited[j] = true; } } // int d = getDistance(last, i); // int x1 = location[last] + d; // int j; // for (int k : v) { // if (location[k] < x1) { // j = k; // break; // } // } // if (getDistance(j, i) + dist1[j] != dist1[i]) { // stype[i] = 1; // location[i] = location[closest] - dist1[i]; // last = i; // v.push_back(i); // } else { // stype[i] = 2; // location[i] = location[closest] - (2 * dist1[j] - dist1[i]); // } } } } //2 10 //1 5 //1 2 //1 1 //1 3 //1 4 //2 7 //2 8 //2 6 //2 9 //2 10 //3 10 //1 3 //1 0 //1 1 //2 2 //1 4 //2 5 //2 6 //1 7 //1 8 //2 9
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...