| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 656081 |
2022-11-06T09:29:24 Z |
Soul234 |
OBELISK (NOI14_obelisk) |
C++14 |
|
75 ms |
24676 KB |
#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];
long long dist1D(long long x, bool useHor, bool useVert) {
if (M == 1) return x;
if (!x) return 0;
if (!useHor && !useVert) return INF;
if (!useHor) return x;
long long v = x / (M + 1);
long long sx = v * (M + 1);
if (sx == x) return 2 * v - 2;
if (!useVert) return INF;
long long fromFront = max(0LL, 2 * v - 2) + x - sx;
long long fromBack = 2 * v + (sx + M + 1) - x;
return min(fromFront, fromBack);
}
long long getDist(pair<int, int> a, pair<int, int> b) {
int x = abs(a.first - b.first), y = abs(a.second - b.second);
long long ans = INF;
for (int useVert = 0; useVert < 2; ++useVert)
for (int useHor = 0; useHor < 2; ++useHor)
ans = min(ans, 2 * (useHor + useVert) + dist1D(x, useHor, useVert) + dist1D(y, useVert, useHor));
return ans;
}
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});
}
}
}
}
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, getDist(lst[fl][i], lst[fl-1][j])});
}
}
// dbg(dist1D(1));
dijkstra(inds[K]);
cout << dist[0] << nl;
}
int main() {
setIO();
int t=1;
//cin>>t;
while(t-->0) {
solve();
}
return 0;
}
Compilation message
obelisk.cpp: In function 'void solve()':
obelisk.cpp:124:21: warning: unused variable 'dx' [-Wunused-variable]
124 | int dx = abs(lst[fl][i].fi - lst[fl-1][j].fi), dy = abs(lst[fl][i].se - lst[fl-1][j].se);
| ^~
obelisk.cpp:124:64: warning: unused variable 'dy' [-Wunused-variable]
124 | int dx = abs(lst[fl][i].fi - lst[fl-1][j].fi), dy = abs(lst[fl][i].se - lst[fl-1][j].se);
| ^~
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 |
| 1 |
Correct |
4 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
8252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8252 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8388 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8508 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8532 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8892 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
21960 KB |
Output is correct |
| 2 |
Correct |
69 ms |
23820 KB |
Output is correct |
| 3 |
Correct |
68 ms |
23140 KB |
Output is correct |
| 4 |
Correct |
69 ms |
23684 KB |
Output is correct |
| 5 |
Correct |
73 ms |
24384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
23040 KB |
Output is correct |
| 2 |
Correct |
70 ms |
22720 KB |
Output is correct |
| 3 |
Correct |
68 ms |
23116 KB |
Output is correct |
| 4 |
Correct |
75 ms |
24676 KB |
Output is correct |
| 5 |
Correct |
74 ms |
23548 KB |
Output is correct |
