| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 199557 |
2020-02-02T03:07:24 Z |
arnold518 |
물병 (JOI14_bottle) |
C++14 |
|
585 ms |
51288 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2000;
const int MAXP = 2e5;
const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};
int H, W, P, QQ;
char S[MAXN+10][MAXN+10];
pii dist[MAXN+10][MAXN+10];
vector<pii> adj[MAXP+10];
struct UF
{
int par[MAXP+10];
UF() { for(int i=1; i<=MAXP; i++) par[i]=i; }
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }
}uf;
int par[MAXP+10][30], dep[MAXP+10], val[MAXP+10][30];
bool vis[MAXN+10];
void dfs(int now, int bef, int depth)
{
vis[now]=true;
dep[now]=depth;
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
par[nxt.first][0]=now;
val[nxt.first][0]=nxt.second;
dfs(nxt.first, now, depth+1);
}
}
int query(int u, int v)
{
int i, j, ans=0;
if(dep[u]>dep[v]) swap(u, v);
for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) ans=max(ans, val[v][i]), v=par[v][i];
if(u==v) return ans;
for(i=20; i>=0; i--) if(par[v][i]!=par[u][i])
{
ans=max(ans, val[v][i]);
ans=max(ans, val[u][i]);
u=par[u][i];
v=par[v][i];
}
ans=max(ans, val[v][0]);
ans=max(ans, val[u][0]);
return ans;
}
int main()
{
int i, j;
scanf("%d%d%d%d", &H, &W, &P, &QQ);
for(i=1; i<=H; i++) scanf("%s", S[i]+1);
queue<pii> Q;
for(i=1; i<=P; i++)
{
int y, x;
scanf("%d%d", &y, &x);
dist[y][x]={i, 0};
Q.push({y, x});
}
while(!Q.empty())
{
pii now=Q.front(); Q.pop();
for(i=0; i<4; i++)
{
int ny=now.first+dy[i], nx=now.second+dx[i];
if(S[ny][nx]=='#') continue;
if(!(1<=ny && ny<=H && 1<=nx && nx<=W)) continue;
if(dist[ny][nx].first!=0)
{
int c1=dist[ny][nx].first, c2=dist[now.first][now.second].first, d=dist[ny][nx].second+dist[now.first][now.second].second;
if(uf.Find(c1)!=uf.Find(c2))
{
uf.Union(c1, c2);
adj[c1].push_back({c2, d});
adj[c2].push_back({c1, d});
}
}
else
{
dist[ny][nx]=dist[now.first][now.second];
dist[ny][nx].second++;
Q.push({ny, nx});
}
}
}
for(i=1; i<=P; i++)
{
if(vis[i]) continue;
dfs(i, i, 1);
}
for(i=1; i<=20; i++) for(j=1; j<=P; j++) val[j][i]=max(val[j][i-1], val[par[j][i-1]][i-1]), par[j][i]=par[par[j][i-1]][i-1];
while(QQ--)
{
int u, v;
scanf("%d%d", &u, &v);
if(uf.Find(u)!=uf.Find(v)) printf("-1\n");
else printf("%d\n", query(u, v));
}
}
Compilation message
bottle.cpp: In function 'int query(int, int)':
bottle.cpp:45:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, ans=0;
^
bottle.cpp: In function 'int main()':
bottle.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &H, &W, &P, &QQ);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:66:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=H; i++) scanf("%s", S[i]+1);
~~~~~^~~~~~~~~~~~~~
bottle.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &y, &x);
~~~~~^~~~~~~~~~~~~~~~
bottle.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
19820 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
11372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
19960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
585 ms |
51288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
