| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61072 |
2018-07-25T07:37:47 Z |
노영훈(#1760) |
Abduction 2 (JOI17_abduction2) |
C++11 |
|
2228 ms |
525312 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=2010, inf=2e9;
int h, w, q;
int A[MX], B[MX];
const int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
inline bool valid(int a, int b){
return 1<=a && a<=h && 1<=b && b<=w;
}
inline bool valid(int a, int b, int k){
int u=a+dx[k], v=b+dy[k];
return valid(a,b) && valid(u,v);
}
const int VMX=2001*2001*4+1;
inline int f(int a, int b, int t){
return t*2001*2001 + a*2001 + b;
}
ll D[VMX];
vector<int> G[VMX], R[VMX];
int deg[VMX]={};
void solve(){
vector<int> V;
for(int i=1; i<=h; i++)
for(int j=1; j<=w; j++)
for(int k=0; k<4; k++)
if(valid(i,j,k)) V.push_back(f(i,j,k));
for(int v:V) deg[v]=G[v].size();
queue<int> Q;
for(int v:V) if(deg[v]==0) Q.push(v);
while(!Q.empty()){
int v=Q.front(); Q.pop();
for(int x:R[v]){
D[x]=max(D[x], D[v]+1);
deg[x]--;
if(deg[x]==0) Q.push(x);
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>h>>w>>q;
assert(h*w<=5e6);
for(int i=1; i<=h; i++) cin>>A[i];
for(int i=1; i<=w; i++) cin>>B[i];
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
for(int k=0; k<4; k++){
int u=i+dx[k], v=j+dy[k];
if(!valid(u,v)) continue;
int c1=(k%2==0 ? A[i] : B[j]), mx=c1;
for(int l=0; l<4; l++){
if(k==(l+2)%4) continue;
if(!valid(u,v,l)) continue;
int c2=(l%2==0 ? A[u] : B[v]);
mx=max(mx, c2);
}
for(int l=0; l<4; l++){
if(k==(l+2)%4) continue;
if(!valid(u,v,l)) continue;
int c2=(l%2==0 ? A[u] : B[v]);
if(mx==c2){
G[f(i,j,k)].push_back(f(u,v,l));
R[f(u,v,l)].push_back(f(i,j,k));
}
}
}
}
}
solve();
for(int i=1; i<=q; i++){
int a,b; cin>>a>>b;
ll ans=0;
for(int k=0; k<4; k++){
int u=a+dx[k], v=b+dy[k];
if(!valid(u,v)) continue;
ans=max(ans, D[f(a,b,k)]);
}
cout<<ans+1<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2228 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2228 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2228 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1046 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2228 ms |
525312 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
