結果
| 問題 | No.3679 なんかでっかい虫リターンズ |
| コンテスト | |
| ユーザー |
 irinoirino
|
| 提出日時 | 2026-09-09 00:22:42 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 2 ms / 2,000 ms |
| + 622µs | |
| コード長 | 5,652 bytes |
| 記録 | |
| コンパイル時間 | 2,035 ms |
| コンパイル使用メモリ | 242,148 KB |
| 実行使用メモリ | 6,528 KB |
| 最終ジャッジ日時 | 2026-09-09 00:22:48 |
| 合計ジャッジ時間 | 3,436 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
In file included from main.cpp:24:
/home/linuxbrew/.linuxbrew/Cellar/gcc@15/15.3.0/include/c++/15/cstdbool:50:6: warning: #warning "<cstdbool> is deprecated in C++17, remove the #include" [-Wcpp]
50 | # warning "<cstdbool> is deprecated in C++17, remove the #include"
| ^~~~~~~
ソースコード
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <tuple>
#include <map>
#include <bit>
#include <array>
#include <limits>
#include <type_traits>
#include <utility>
#include <functional>
#include <fstream>
#include <climits>
#include <numeric>
#include <cassert>
#include <cstdbool>
#include <cstdint>
#include <random>
//#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define orep(i,n) for(ll i=1;i<=(n);i++)
#define nfor(i,s,n) for(ll i=(s);i<(n);i++)
#define dfor(i,s,n) for(ll i=(s)-1;i>=n;i--)
#define INF 2000000000000000000//9223372036854775807
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pb push_back
#define pob pop_back
#define vc vector
#define for_sz(s) (long long)(s.size())
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
#define YN {cout << "Yes" << endl;}else{cout << "No" << endl;}
#define dame cout << -1 << endl;
#define vc_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define vc_remove(v,x) v.erase(remove(v.begin(), v.end(),x), v.end())
#define vc_rotate(v) rotate(v.begin(), v.begin()+1, v.end())
#define pop_cnt(s) ll(popcount(uint64_t(s)))
#define next_p(v) next_permutation(v.begin(),v.end())
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
using namespace std;
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll,ll>;
using vvvvvl = vector<vector<vector<vector<vector<ll> > > > >;
using vvvvl = vector<vector<vector<vector<ll> > > >;
using vvvl = vector<vector<vector<ll> > >;
using vvl = vector<vector<ll> >;
using vl = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool> >;
using Graph = vector<vector<ll> >;
template<class T> using pq = priority_queue<T,vc<T>,less<T> >;
template<class T> using pq_g = priority_queue<T,vc<T>,greater<T> >;
ll dx[4] = {0,1,0,-1};ll ddx[8] = {1,1,0,-1,-1,-1,0,1};
ll dy[4] = {1,0,-1,0};ll ddy[8] = {0,1,1,1,0,-1,-1,-1};
bool out_grid(ll i, ll j, ll h, ll w){//trueならcontinueする
return(!(0 <= i && i < h && 0 <= j && j<w));
}
template<class T>
void cutoutV(vc<vc<T>> &G, ll H, ll W, ll mx, ll Mx, ll my, ll My){
if(!(0 <= mx && mx < H && 0 < Mx && Mx <= H && mx < Mx))return;
if(!(0 <= my && my < H && 0 < My && My <= H && my < My))return;
rep(i,Mx - mx)rep(j,My - my){
G[i][j] = G[i + mx][j + my];
}
G.resize(Mx - mx, vc<T>(My - my));
return;
}
ll modpow(ll x,ll y,ll m){
ll a = x;
a %= m;
ll cnt = 0;
ll ans = 1;
while(y > 0){
if((1ll << cnt) & y){
y ^= (1ll << cnt);
ans *= a;
ans %= m;
}
a = a*a;
a %= m;
cnt++;
}
return ans;
}
ll npow(ll x,ll y){
ll a = x;
ll cnt = 0;
ll ans = 1;
while(y > 0){
if((1ll << cnt) & y){
y ^= (1ll << cnt);
ans *= a;
}
a = a*a;
cnt++;
}
return ans;
}
struct Edge {
ll to;
ll cost;
};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
// ai+bj=g
// ai+bj=gcd(a,b)なるi,jを求める
ll extgcd(ll a, ll b, ll& i, ll& j) {
if (b == 0) { i = 1; j = 0; return a;}
ll p = a/b, g = extgcd(b,a-b*p,j,i);
j -= p*i;
return g;
}
vl topological_sort(const vvl& G){
ll N = (ll)G.size();
vl indeg(N, 0), order;
queue<ll> que;
rep(u, N){
for(ll v : G[u]) indeg[v]++;
}
rep(i, N){
if(indeg[i] == 0) que.push(i);
}
while(!que.empty()){
ll u = que.front();
que.pop();
order.pb(u);
for(ll v : G[u]){
indeg[v]--;
if(indeg[v] == 0) que.push(v);
}
}
return order;
}
ll MOD = 998244353;
void print(ld x){printf("%.20Lf\n", x);}
//using mint = modint998244353;
////////////////////////////////////////////////////////////////
int main(){
ll H,W;
cin >> H >> W;
pll start;
cin >> start.fi >> start.se;
pll left;
cin >> left.fi >> left.se;
pll right;
cin >> right.fi >> right.se;
pll gomi;
cin >> gomi.fi >> gomi.se;
queue<pll> que;
vvl dist1(H,vl(W,INF));
vvl dist2(H,vl(W,INF));
dist1[start.fi-1][start.se-1] = 0;
dist2[gomi.fi-1][gomi.se-1] = 0;
que.push({start.fi-1,start.se-1});
while(!que.empty()){
auto [x,y] = que.front();
que.pop();
rep(i,4){
ll nx = x + dx[i];
ll ny = y + dy[i];
if(out_grid(nx,ny,H,W))continue;
if(dist1[nx][ny] <= dist1[x][y] + 1)continue;
dist1[nx][ny] = dist1[x][y] + 1;
que.push({nx,ny});
}
}
que.push({gomi.fi-1,gomi.se-1});
while(!que.empty()){
auto [x,y] = que.front();
que.pop();
rep(i,4){
ll nx = x + dx[i];
ll ny = y + dy[i];
if(out_grid(nx,ny,H,W))continue;
if(dist2[nx][ny] <= dist2[x][y] + 1)continue;
dist2[nx][ny] = dist2[x][y] + 1;
que.push({nx,ny});
}
}
ll ans = INF;
rep(i,H)rep(j,W){
if(left.fi <= i+1 && i+1 <= right.fi && left.se <= j+1 && j+1 <= right.se){
chmin(ans,dist1[i][j] + dist2[i][j]);
}
}
cout << ans + abs(start.fi - gomi.fi) + abs(start.se - gomi.se) << endl;
}