| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1167463 | yeediot | 물병 (JOI14_bottle) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
freopen("/Users/iantsai/cpp/input.txt","r",stdin);
freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn = 2005, inf = 1e18;
int g[mxn][mxn], val[mxn * mxn * 2], jump[23][mxn * mxn * 2], dep[mxn * mxn * 2];
array<int, 2> dis[mxn][mxn];
vector<int>adj[mxn * mxn * 2];
struct DSU{
int to[mxn * mxn * 2];
void init(){
for(int i = 0; i < mxn * mxn * 2; i++){
to[i] = -1;
}
}
int find(int x){
return to[x] < 0 ? x : to[x] = find(to[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return;
to[y] += to[x];
to[x] = y;
}
}d;
void solve(){
d.init();
int n, m, p, q;
cin >> n >> m >> p >> q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char c;
cin >> c;
g[i][j] = (c == '.');
dis[i][j] = {inf, inf};
}
}
queue<array<int, 2>>qu;
for(int i = 1; i <= p; i++){
int x, y;
cin >> x >> y;
dis[x][y] = {0, i};
qu.push({x, y});
debug(x, y);
}
vector<int>dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
auto valid = [&](int x, int y){
return 1 <= x and x <= n and 1 <= y and y <= m and g[x][y];
};
while(sz(qu)){
auto [x, y] = qu.front();
qu.pop();
if(dis[x][y][0] == inf) continue;
int d = dis[x][y][0] + 1, id = dis[x][y][1];
for(int r = 0; r < 4; r++){
int nx = x + dx[r], ny = y + dy[r];
if(!valid(nx, ny)) continue;
auto [od, oid] = dis[nx][ny];
if(od > d){
dis[nx][ny] = {d, id};
qu.push({nx, ny});
}
}
}
vector<array<int, 3>>e;
auto conv = [&](int x, int y){
return (x - 1) * n + y;
};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(dis[i][j][0] >= inf) continue;
int nx = i + 1, ny = j;
auto [d, id] = dis[i][j];
if(valid(nx, ny)){
if(dis[nx][ny][1] != id){
e.pb({dis[nx][ny][0] + d, id, dis[nx][ny][1]});
}
}
nx = i, ny = j + 1;
if(valid(nx, ny)){
if(dis[nx][ny][1] != id){
e.pb({dis[nx][ny][0] + d, id, dis[nx][ny][1]});
}
}
}
}
sort(all(e));
debug(e);
int cnt = p;
for(auto [w, a, b] : e){
a = d.find(a), b = d.find(b);
if(a == b) continue;
val[++cnt] = w;
d.merge(a, cnt);
d.merge(b, cnt);
adj[cnt].pb(a);
adj[cnt].pb(b);
}
function<void(int)> dfs = [&](int v){
if(!jump[0][v]) jump[0][v] = v;
for(auto u : adj[v]){
dep[u] = dep[v] + 1;
jump[0][u] = v;
debug(u, v);
dfs(u);
}
};
auto lca = [&](int x, int y){
if(dep[x] < dep[y]) swap(x, y);
int dif = dep[x] - dep[y];
for(int i = 22; i >= 0; i--){
if(dif >> i & 1) x = jump[i][x];
}
if(x == y) return val[x];
for(int i = 22; i >= 0; i--){
if(jump[i][x] != jump[i][y]){
x = jump[i][x];
y = jump[i][y];
}
}
debug(x, jump[0][x]);
return val[jump[0][x]];
};
for(int i = 1; i <= cnt; i++){
if(d.find(i) == i) dfs(i);
}
for(int k = 1; k < 23; k++){
for(int i = 1; i <= cnt; i++){
jump[k][i] = jump[k - 1][jump[k - 1][i]];
}
}
for(int i = 0; i < q; i++){
int s, t;
cin >> s >> t;
if(d.find(s) != d.find(t)){
cout << -1 << '\n';
continue;
}
cout << lca(s, t) << '\n';
}
}
signed main(){
TOI_is_so_de;
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef local
CHECK();
#endif
}
/*
input:
*/
#ifdef local
void CHECK(){
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
std::ifstream file1(p1);
std::ifstream file2(p2);
if(!file1.is_open() || !file2.is_open()) return false;
std::string line1, line2;
while (getline(file1, line1) && getline(file2, line2)) {
if (line1 != line2)return false;
}
int cnta = 0, cntb = 0;
while(getline(file1,line1))cnta++;
while(getline(file2,line2))cntb++;
return cntb - cnta <= 1;
};
bool check = compareFiles("output.txt","expected.txt");
if(check) cerr<<"ACCEPTED\n";
else cerr<<"WRONG ANSWER!\n";
}
#else