| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 287104 | egekabas | 철로 (IOI14_rail) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int d[5009][5009];
int vis[5009];
set<pii> bef;
int n;
void dfs(int v, int l, int t, int loc[], int stype[]){
stype[v] = t;
loc[v] = l;
if(t == 1){
vis[v] = 1;
bef.insert({l, v});
}
pii mini = {1e9, 1e9};
for(int i = 0; i < n; ++i)
if(!vis[i] && i != v)
mini = min(mini, {d[v][i], i});
//cout << v << ' ' << l << ' ' << t << ' ' << mini.ff << ' ' << mini.ss << '\n';
if(mini.ff == 1e9)
return;
if(t == 1){
dfs(mini.ss, l+mini.ff, 2, loc, stype);
return;
}
auto it = bef.lower_bound({l, 0});
if(it != bef.begin()){
--it;
if(mini.ff == l-it->ff+d[it->ss][mini.ss]){
vis[v] = 1;
dfs(mini.ss, it->ff+d[it->ss][mini.ss], 2, loc, stype);
return;
}
}
dfs(mini.ss, l-mini.ff, 1, loc, stype);
}
void findLocation(int N, int first, int location[], int stype[]){
//cout << '\n';
n = N;
for(int i = 0; i < n; ++i)
for(int j = i+1; j < n; ++j)
d[i][j] = d[j][i] = getDistance(i, j);
dfs(0, first, 1, location, stype);
//cout << '\n';
//for(int i = 0; i < n; ++i)
// cout << stype[i] << ' ' << location[i] << '\n';
}