제출 #883502

#제출 시각아이디문제언어결과실행 시간메모리
883502ono_de206철로 (IOI14_rail)C++14
30 / 100
81 ms98560 KiB
#include "rail.h" #include<bits/stdc++.h> using namespace std; #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second //#define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; void findLocation(int n, int first, int pos[], int tp[]) { pos[0] = first; tp[0] = 1; if(n == 1) return; vector<vector<int>> dis(n, vector<int>(n, -1)); auto get = [&](int x, int y) -> int { if(x > y) swap(x, y); if(dis[x][y] != -1) return dis[x][y]; return dis[x][y] = getDistance(x, y); }; vector<int> id(n - 1); iota(all(id), 1); sort(all(id), [&](int x, int y) { return get(0, x) < get(0, y); }); vector<int> res; int ls = id[0], tmp = id[0]; id.erase(id.begin()); tp[ls] = 2; pos[ls] = pos[0] + get(0, ls); for(int x : id) { if(get(0, x) + get(0, ls) == get(x, ls)) { tp[x] = 2; pos[x] = pos[0] + get(0, x); ls = x; } else { if(pos[ls] - get(ls, x) >= pos[0]) { tp[x] = 1; pos[x] = pos[ls] - get(ls, x); } else { res.pb(x); } } } if(res.size()) { int ls = res[0]; res.erase(res.begin()); tp[ls] = 1; pos[ls] = pos[0] - get(0, ls) + 2 * get(0, tmp); for(int x : res) { if(get(0, x) + get(0, ls) - 2 * get(0, tmp) == get(ls, x)) { tp[x] = 1; pos[x] = pos[0] - get(0, x) + 2 * get(0, tmp); ls = x; } else { tp[x] = 2; pos[x] = pos[ls] + get(ls, x); } } } // for(int i = 0; i < n; i++) { // assert(pos[i] >= 0 && pos[i] < 1000000); // } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...