oj.uz

Submission #17352

# Submission time Handle Problem Language Result Execution time Memory
17352 2015-11-25T12:09:03 Z eaststar Cop and Robber (BOI14_coprobber) C++14
60 / 100
 385 ms 5104 KB 
#include "coprobber.h"
#include <queue>
using namespace std;
struct data{
    int x,y,z;
}t;
queue<data> q;
int a[510][510][2],nx[510][510],p;
int start(int N, bool A[MAX_N][MAX_N]){
    int i,j,cnt;
    for(i=0;i<N;++i){
        cnt=0;
        for(j=0;j<N;++j)if(A[i][j])++cnt;
        for(j=0;j<N;++j)if(i!=j)a[j][i][0]=1,a[j][i][1]=cnt;
        q.push({i,i,0}),q.push({i,i,1});
    }
    while(!q.empty()){
        t=q.front();
        q.pop();
        if(t.z){
            for(i=0;i<N;++i)if((t.x==i||A[t.x][i])&&a[i][t.y][0]){
                --a[i][t.y][0];
                if(!a[i][t.y][0])q.push({i,t.y,0}),nx[i][t.y]=t.x;
            }
        }
        else{
            for(i=0;i<N;++i)if(A[t.y][i]&&a[t.x][i][1]){
                --a[t.x][i][1];
                if(!a[t.x][i][1])q.push({t.x,i,1});
            }
        }
    }
    for(i=0;i<N;++i){
        for(j=0;j<N;++j)if(a[i][j][0])break;
        if(j==N)return p=i;
    }
    return -1;
}
int nextMove(int R){
    return p=nx[p][R];
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 328 ms 4708 KB Output is correct
5 Correct 50 ms 2556 KB Output is correct
6 Correct 385 ms 5104 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 326 ms 4752 KB Output is correct
4 Correct 332 ms 4732 KB Output is correct
5 Correct 335 ms 4736 KB Output is correct
6 Correct 345 ms 4588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 5 ms 1024 KB Output is correct
15 Correct 3 ms 740 KB Output is correct
16 Correct 3 ms 768 KB Output is correct
17 Correct 9 ms 1280 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 332 ms 4712 KB Output is correct
5 Correct 119 ms 2424 KB Output is correct
6 Runtime error 82 ms 4580 KB Execution killed with signal 2 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -