이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if(sizeof...(t)) cerr << ", ";
DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL
#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;
void setIO(string NAME = "") {
cin.tie(0)->sync_with_stdio(0);
if(sz(NAME)) {
freopen((NAME + ".inp").c_str(),"r",stdin);
freopen((NAME + ".out").c_str(),"w",stdout);
}
}
tcT> bool ckmin(T&a, const T&b) {
return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
return b > a ? a=b,1 : 0; }
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int MX = 505;
int K, M;
V<pi> lst[MX];
int sx, sy, ex, ey;
int inds[MX];
V<pi> adj[MX*MX];
ll dist[MX*MX];
void dijkstra(int src) {
memset(dist, 0x3f, sizeof dist);
pqg<pair<ll,int>> pq;
pq.push({dist[src] = 0, src});
while(sz(pq)) {
ll du = pq.top().fi;
int u = pq.top().se;
pq.pop();
if(du > dist[u]) continue;
each(ed, adj[u]) {
int v = ed.fi;
ll dv = dist[u] + ed.se;
if(ckmin(dist[v], dv)) {
pq.push({dv, v});
}
}
}
}
int dist1D(int delta, bool hor, bool ver) {
if(M == 1) return delta;
if(delta == 0) return 0;
if(!hor && !ver) return MOD;
if(!hor) return delta;
int need = delta/(M+1);
int sx = need*(M+1);
if(delta == sx) return 2*need - 2;
if(!ver) return MOD;
int opt1 = max(0, 2*need - 2) + delta - sx;
int opt2 = 2*need + sx + M + 1 - delta;
return min(opt1, opt2);
}
int dist2D(int dx, int dy) {
int res = INT_MAX;
F0R(i, 2) F0R(j, 2) {
ckmin(res, 2*(i + j) + dist1D(dx, i, j) + dist1D(dy, j, i));
}
return res;
}
void solve() {
cin >> K >> M;
cin >> sx >> sy >> ex >> ey;
lst[0] = {{ex, ey}};
lst[K] = {{sx, sy}};
ROF(i,1,K) {
int num;
cin >> num;
lst[i].resize(num);
F0R(j, num) {
cin >> lst[i][j].fi >> lst[i][j].se;
}
}
F0R(i, K) inds[i+1] = inds[i] + sz(lst[i]);
FOR(fl,1,K+1) {
F0R(i, sz(lst[fl]))
F0R(j, sz(lst[fl-1])) {
int dx = abs(lst[fl][i].fi - lst[fl-1][j].fi), dy = abs(lst[fl][i].se - lst[fl-1][j].se);
// dbg(dx, dy, dist2D(dx, dy));
adj[inds[fl]+i].pb({inds[fl-1]+j, dist2D(dx, dy)});
}
}
// dbg(dist1D(1));
dijkstra(inds[K]);
cout << dist[0] << nl;
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
obelisk.cpp: In function 'void setIO(std::string)':
obelisk.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((NAME + ".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
obelisk.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((NAME + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |