oj.uz

답안 #61073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61073 2018-07-25T07:39:00 Z 노영훈(#1760) 유괴 2 (JOI17_abduction2) C++11
0 / 100
 2148 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;
}

int 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;
        int 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;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2148 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 -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2148 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 -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2148 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 -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1149 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2148 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 -