oj.uz

답안 #61082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61082 2018-07-25T07:45:59 Z 노영훈(#1760) 유괴 2 (JOI17_abduction2) C++11
13 / 100
 4865 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, TMP=2001;

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=TMP*TMP*4+1;
inline int f(int a, int b, int t){
    return t*TMP*TMP + a*TMP + b;
}

int D[VMX];
vector<int> R[VMX];
uint8_t deg[VMX]={};
queue<int> Q;

void solve(){
    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)){
                    int v=f(i,j,k);
                    for(int x:R[v]) deg[x]++;
                }
    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)){
                    int v=f(i,j,k);
                    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
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 376700 KB Output is correct
2 Correct 374 ms 376932 KB Output is correct
3 Correct 425 ms 376932 KB Output is correct
4 Correct 354 ms 376932 KB Output is correct
5 Correct 349 ms 376932 KB Output is correct
6 Correct 405 ms 376932 KB Output is correct
7 Correct 350 ms 376992 KB Output is correct
8 Correct 375 ms 376992 KB Output is correct
9 Correct 392 ms 376992 KB Output is correct
10 Correct 365 ms 376992 KB Output is correct
11 Correct 423 ms 376992 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 376700 KB Output is correct
2 Correct 374 ms 376932 KB Output is correct
3 Correct 425 ms 376932 KB Output is correct
4 Correct 354 ms 376932 KB Output is correct
5 Correct 349 ms 376932 KB Output is correct
6 Correct 405 ms 376932 KB Output is correct
7 Correct 350 ms 376992 KB Output is correct
8 Correct 375 ms 376992 KB Output is correct
9 Correct 392 ms 376992 KB Output is correct
10 Correct 365 ms 376992 KB Output is correct
11 Correct 423 ms 376992 KB Output is correct
12 Execution timed out 4865 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 376700 KB Output is correct
2 Correct 374 ms 376932 KB Output is correct
3 Correct 425 ms 376932 KB Output is correct
4 Correct 354 ms 376932 KB Output is correct
5 Correct 349 ms 376932 KB Output is correct
6 Correct 405 ms 376932 KB Output is correct
7 Correct 350 ms 376992 KB Output is correct
8 Correct 375 ms 376992 KB Output is correct
9 Correct 392 ms 376992 KB Output is correct
10 Correct 365 ms 376992 KB Output is correct
11 Correct 423 ms 376992 KB Output is correct
12 Execution timed out 4865 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4740 ms 525312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 397 ms 376700 KB Output is correct
2 Correct 374 ms 376932 KB Output is correct
3 Correct 425 ms 376932 KB Output is correct
4 Correct 354 ms 376932 KB Output is correct
5 Correct 349 ms 376932 KB Output is correct
6 Correct 405 ms 376932 KB Output is correct
7 Correct 350 ms 376992 KB Output is correct
8 Correct 375 ms 376992 KB Output is correct
9 Correct 392 ms 376992 KB Output is correct
10 Correct 365 ms 376992 KB Output is correct
11 Correct 423 ms 376992 KB Output is correct
12 Execution timed out 4865 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -