oj.uz

Submission #61075

# Submission time Handle Problem Language Result Execution time Memory
61075 2018-07-25T07:40:57 Z 노영훈(#1760) Abduction 2 (JOI17_abduction2) C++11
13 / 100
 4803 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];
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) for(int x:R[v]) deg[x]++;

    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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 376784 KB Output is correct
2 Correct 365 ms 376808 KB Output is correct
3 Correct 411 ms 376976 KB Output is correct
4 Correct 348 ms 377004 KB Output is correct
5 Correct 382 ms 377116 KB Output is correct
6 Correct 374 ms 377116 KB Output is correct
7 Correct 346 ms 377164 KB Output is correct
8 Correct 347 ms 377164 KB Output is correct
9 Correct 366 ms 377164 KB Output is correct
10 Correct 344 ms 377184 KB Output is correct
11 Correct 332 ms 377184 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 376784 KB Output is correct
2 Correct 365 ms 376808 KB Output is correct
3 Correct 411 ms 376976 KB Output is correct
4 Correct 348 ms 377004 KB Output is correct
5 Correct 382 ms 377116 KB Output is correct
6 Correct 374 ms 377116 KB Output is correct
7 Correct 346 ms 377164 KB Output is correct
8 Correct 347 ms 377164 KB Output is correct
9 Correct 366 ms 377164 KB Output is correct
10 Correct 344 ms 377184 KB Output is correct
11 Correct 332 ms 377184 KB Output is correct
12 Execution timed out 4205 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 376784 KB Output is correct
2 Correct 365 ms 376808 KB Output is correct
3 Correct 411 ms 376976 KB Output is correct
4 Correct 348 ms 377004 KB Output is correct
5 Correct 382 ms 377116 KB Output is correct
6 Correct 374 ms 377116 KB Output is correct
7 Correct 346 ms 377164 KB Output is correct
8 Correct 347 ms 377164 KB Output is correct
9 Correct 366 ms 377164 KB Output is correct
10 Correct 344 ms 377184 KB Output is correct
11 Correct 332 ms 377184 KB Output is correct
12 Execution timed out 4205 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4803 ms 525312 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 376784 KB Output is correct
2 Correct 365 ms 376808 KB Output is correct
3 Correct 411 ms 376976 KB Output is correct
4 Correct 348 ms 377004 KB Output is correct
5 Correct 382 ms 377116 KB Output is correct
6 Correct 374 ms 377116 KB Output is correct
7 Correct 346 ms 377164 KB Output is correct
8 Correct 347 ms 377164 KB Output is correct
9 Correct 366 ms 377164 KB Output is correct
10 Correct 344 ms 377184 KB Output is correct
11 Correct 332 ms 377184 KB Output is correct
12 Execution timed out 4205 ms 525312 KB Time limit exceeded (wall clock)
13 Halted 0 ms 0 KB -