| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 940548 | vjudge1 | 웜뱃 (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma once
#include <bits/stdc++.h>
#define f first
#define s second
const int INF = 1e9 + 7;
using namespace std;
const int G = 200000 + 10;
int n,m;
set <pair <int,int> > reb[G];
int A[5000][200],B[5000][200];
void init(int R, int C,int H[5000][200], int V[5000][200]) {
n = R,m = C;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m - 1;j++) {
reb[i*m + j].insert({i*m + j + 1,H[i][j]});
reb[i*m + j + 1].insert({i*m + j,H[i][j]});
}
}
for(int i = 0;i < R;i++) {
for(int j = 0;j < C;j++) {
A[i][j] = H[i][j];
B[i][j] = V[i][j];
}
}
for(int i = 0;i < n - 1;i++) {
for(int j = 0;j < m;j++) {
reb[i*m + j].insert({(i + 1)*m + j,V[i][j]});
}
}
};
void changeH(int P, int Q, int W) {
int v1 = P*m + Q,v2 = P*m + Q + 1;
reb[v1].erase({A[P][Q],v2});
reb[v2].erase({A[P][Q],v1});
A[P][Q] = W;
reb[v1].insert({A[P][Q],v2});
reb[v2].insert({A[P][Q],v1});
};
void changeV(int P, int Q, int W) {
int v1 = P*m + Q,v2 = (P + 1)*m + Q;
reb[v1].erase({B[P][Q],v2});
reb[v2].erase({B[P][Q],v1});
B[P][Q] = W;
reb[v1].insert({B[P][Q],v2});
reb[v2].insert({B[P][Q],v1});
};
int dijkstra(int x,int y) {
int rast[n*m] = {};
for(int i = 0;i < n*m;i++) {
rast[i] = INF;
}
rast[x] = 0;
set <pair <int,int> > s;
s.insert({0,x});
while(!s.empty()) {
pair <int,int> v = *s.begin();
s.erase(s.find(v));
for(auto u:reb[v.s]) {
int rst = u.s + v.f;
if(rst < rast[u.f]) {
s.erase({rast[u.f],u.f});
rast[u.f] = rst;
s.insert({rast[u.f],u.f});
}
}
}
return rast[m*(n - 1) + y];
}
int escape(int V1, int V2) {
int x = V1,y = V2;
return dijkstra(x,y);
};
/*
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m - 1;j++) {
cin >> H[i][j];
}
}
for(int i = 0;i < n - 1;i++) {
for(int j = 0;j < m;j++) {
cin >> V[i][j];
}
}
init(n,m);
int q;
cin >> q;
while(q--) {
int type;
cin >> type;
if(type == 3) {
int x,y;
cin >> x >> y;
cout << escape(x,y) << endl;
}
else {
int a,b,c;
cin >> a >> b >> c;
}
}
}
*/