# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
750631 | Abrar_Al_Samit | 철로 (IOI14_rail) | C++17 | 90 ms | 54912 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 5000;
int mem[nax][nax];
int know[nax];
int get(int a, int b) {
if(a==b) return 0;
if(mem[a][b]) return mem[a][b];
return mem[a][b] = mem[b][a] = getDistance(a, b);
}
void solve(int N, int leftMost, int location[], int stype[]) {
while(1) {
bool yes = false;
for(int i=0; i<N; ++i) {
if(!know[i]) yes = true;
}
if(!yes) break;
int ndt;
int dis = 1e9;
for(int i=0; i<N; ++i) if(!know[i]) {
if(dis>get(leftMost, i)) {
dis = get(leftMost, i);
ndt = i;
}
}
location[ndt] = location[leftMost] + dis;
stype[ndt] = 2;
know[ndt] = 1;
for(int i=0; i<N; ++i) if(!know[i]) {
int d1 = get(leftMost, ndt);
int d2 = get(ndt, i);
if(get(leftMost, i)==d1+d2) {
know[i] = 1;
location[i] = location[ndt] - d2;
stype[i] = 1;
}
}
}
}
void findLocation(int N, int first, int location[], int stype[]) {
location[0] = first, stype[0] = 1;
know[0] = 1;
int ndt;
int dis = 1e9;
for(int i=1; i<N; ++i) {
if(get(0, i)<dis) {
dis = get(0, i);
ndt = i;
}
}
location[ndt] = first + dis, stype[ndt] = 2;
know[ndt] = 1;
int vf = 0, loc = first;
for(int i=1; i<N; ++i) {
int d1 = get(0, i);
int d2 = get(ndt, i);
if(d1==get(0, ndt)+d2) {
if(location[ndt]-d2<loc) {
vf = i;
loc = location[ndt]-d2;
}
}
}
know[0] = know[ndt] = 0;
location[vf] = loc;
stype[vf] = 1;
know[vf] = 1;
solve(N, vf, location, stype);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |