제출 #1042825

#제출 시각아이디문제언어결과실행 시간메모리
1042825ALeonidou철로 (IOI14_rail)C++17
30 / 100
285 ms98744 KiB
#include "rail.h" #include <bits/stdc++.h> using namespace std; #define ll int #define F first #define S second #define sz(x) (ll)x.size() #define endl "\n" #define pb push_back typedef vector <ll> vi; typedef pair <ll,ll> ii; typedef vector <ii> vii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i =0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } ll n, found; vector <vi> arr; vi vis; inline void visit(ll idx, ll p, ll t, ll pos[], ll type[]){ vis[idx] = 1; pos[idx] = p; type[idx] = t; found++; } void init_left_and_right(ll &l, ll &r, vi &left, vi &right, ll pos[], ll type[]){ // dbg2(l,r); left.clear(), right.clear(); for (ll i =0; i<n; i++){ if (!vis[i]){ ll a = arr[l][i]; ll b = arr[r][i]; // dbg3(i,a,b); if (a < b){ right.pb(i); } else{ if (arr[l][r] > arr[r][i]){ //initial in between case: visit(i, pos[r] - b, 1, pos, type); l = i; init_left_and_right(i,r,left,right,pos,type); return; } else{ left.pb(i); } } } } } void solve(ll &l, ll &r, ll pos[], ll type[], vi &left, vi &right){ //Time complexity: O(n) // dbg3(found,l,r); //update left ll miniLeft = -1, miniRight = -1; vi tmp_right, tmp_left; for (ll i =0; i<sz(left); i++){ ll c = left[i]; if (!vis[c]){ tmp_left.pb(c); if (miniLeft == -1 || arr[l][miniLeft] > arr[l][c]){ miniLeft = c; } } } //update right for (ll i =0; i<sz(right); i++){ ll c = right[i]; if (!vis[c]){ tmp_right.pb(c); if (miniRight == -1 || arr[l][miniRight] > arr[l][c]){ miniRight = c; } } } left = tmp_left; right = tmp_right; // cout<<"left:"; // printVct(left); // cout<<"right:"; // printVct(right); if (sz(left)){ //left ll newLeft = miniLeft; ll mini_left_from_new_left = -1; // dbg(newLeft); visit(newLeft, pos[r] - arr[r][newLeft], 1, pos, type); for (ll i =0; i<sz(left); i++){ if (vis[left[i]]) continue; if (mini_left_from_new_left == -1 || arr[newLeft][mini_left_from_new_left] > arr[newLeft][left[i]]){ mini_left_from_new_left = left[i]; } } // dbg(mini_left_from_new_left); if (mini_left_from_new_left != -1 && arr[newLeft][mini_left_from_new_left] < arr[l][mini_left_from_new_left]){ //C2 visit(mini_left_from_new_left, pos[newLeft] + arr[mini_left_from_new_left][newLeft], 2, pos, type); for (ll i =0; i<sz(left); i++){ if (vis[left[i]]) continue; if (arr[left[i]][mini_left_from_new_left] > arr[left[i]][newLeft]){ visit(left[i], pos[newLeft] + arr[newLeft][left[i]], 2, pos, type); } } } l = newLeft; } else{ //right ll newRight = miniRight; ll mini_right_from_new_right = -1; visit(newRight, pos[l] + arr[l][newRight], 2, pos, type); // dbg(newRight); for (ll i =0; i<sz(right); i++){ if (vis[right[i]]) continue; if (mini_right_from_new_right == -1 || arr[newRight][mini_right_from_new_right] > arr[newRight][right[i]]){ mini_right_from_new_right = right[i]; } } // dbg(mini_right_from_new_right); if (mini_right_from_new_right != -1 && arr[newRight][mini_right_from_new_right] < arr[r][mini_right_from_new_right]){ //C2 visit(mini_right_from_new_right, pos[newRight] - arr[mini_right_from_new_right][newRight], 1, pos, type); for (ll i =0; i<sz(right); i++){ if (vis[right[i]]) continue; if (arr[right[i]][mini_right_from_new_right] > arr[right[i]][newRight]){ visit(right[i], pos[newRight] - arr[newRight][right[i]], 1, pos, type); } } } r = newRight; } } void findLocation(ll N, ll f, ll pos[], ll type[]) { n = N; arr.assign(n, vi(n)); for (ll i = 0; i<n; i++){ for (ll j =0; j<n; j++){ if (i == j) arr[i][j] = 0; else if (i > j) arr[i][j] = arr[j][i]; else arr[i][j] = getDistance(i,j); } } // for (ll i =0; i<n; i++){ // cout<<i<<": "; // for (ll j =0; j<n;j++){ // cout<<arr[i][j]<<" "; // } // cout<<endl; // } vis.assign(n, 0); vii v0; for (ll i =1; i<n; i++){ v0.pb(ii(arr[0][i], i)); } sort(v0.begin(), v0.end()); ll first_right = v0[0].S; visit(0, f, 1, pos, type); visit(first_right, f + v0[0].F, 2, pos, type); vi left, right; ll l = 0, r = first_right; init_left_and_right(l, r, left, right, pos, type); // printVct(vis); while (found < n){ // cout<<endl; // printVct(vis); solve(l,r,pos,type,left,right); // cout<<endl; } // for (ll i =0; i<n; i++){ // cout<<pos[i]<<" "; // } // cout<<endl; // for (ll i =0; i<n; i++){ // cout<<type[i]<<" "; // } // cout<<endl; } /* 3 6 1 0 2 9 1 3 2 2 1 4 2 5 3 4 1 0 2 8 1 7 2 9 3 3 1 3 2 9 2 1 3 5 1 5 2 8 2 6 2 7 1 2 3 5 1 5 1 2 1 6 2 3 2 8 2 3 4 1 5 2 6 2 1 4 1 1 2 4 2 7 2 9 2 6 1 3 2 6 2 7 1 1 1 0 2 8 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...