oj.uz

Submission #483281

# Submission time Handle Problem Language Result Execution time Memory
483281 2021-10-28T13:09:46 Z MohamedFaresNebili Cop and Robber (BOI14_coprobber) C++14
16 / 100
 48 ms 1676 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "coprobber.h"

        using namespace std;
        using namespace __gnu_pbds;

        using ll  = long long;
        using ld  = long double;
        using ii  = pair<ll, ll>;
        using ull = unsigned long long;

        using vl  = vector<long long>;

        #define mp make_pair
        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define ub upper_bound
        #define all(x) (x).begin() , (x).end()
        #define vi vector<int>

        const int N = 2*100005;
        const long long MOD = 1000000007;
        const long double EPS = 0.000000001;
        const double PI = 3.14159265358979323846;
        const long long INF = 10000000000000000;
        const int nx[2]={1, 0}, ny[2]={0, 1};

        long long gcd(int a, int b) { return (b==0?a:gcd(b, a%b)); }
        long long lcm(int a, int b) { return  a*(b/gcd(a, b)); }
        long long fact(int a) { return (a==1?1:a*fact(a-1)); }

        template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

        #define MAX_N 500

        vector<int>adj[MAX_N];

        int Police = 0;
        map<pair<int, int>, bool>used;
        bitset<524>prime;
        void init() {
            prime[1] = prime[0] = 1;
            for(int l = 2; l <= 500; l++) {
                for(int i = 2; i * l <= 500; i++)
                    prime[l*i] = 1;
            }
        }
        bool grid(int N) {
            if(!prime[N]) return 0;
            int a = 0, b = 0, c = 0;
            for(int l = 0; l < N; l++) {
                int sz = (int)adj[l].size();
                a+=(sz==2);
                b+=(sz==3);
                c+=(sz==4);
            }
            if(a!=4||a+b+c!=N) return 0;
            bool ok = 0;
            for(int l = 2; l * l <= N; l++) {
                if(N % l) continue;
                int curr = l*2 + (N/l)*2 - 4;
                ok |= ((curr == a + b) && (c == N - curr));
            }
            return ok;
        }
        int start(int N, bool A[MAX_N][MAX_N])
        {
            init();
            for(int l = 0; l < N; l++) {
                for(int i=0; i < N; i++) {
                    if(A[l][i]) adj[l].pb(i);
                }
            }
            if(grid(N)) return -1;
            return 0;
        }

        bool dfs(int v, int p, int dest) {
            if(v == dest) return 1;
            for(auto u:adj[v]) {
                if(u == p) continue;
                if(dfs(u, v, dest)) return 1;
            }
            return 0;
        }

        int nextMove(int R)
        {
            for(auto u:adj[Police]) {
                if(u==R||dfs(u, Police, R)) {
                    return Police = u;
                }
            }
            return -1;
        }

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 40 ms 1676 KB Output is correct
5 Correct 9 ms 840 KB Output is correct
6 Correct 48 ms 1592 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 200 KB Cop can catch the robber, but start() returned -1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Incorrect 0 ms 200 KB Cop can catch the robber, but start() returned -1
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 40 ms 1676 KB Output is correct
5 Correct 9 ms 840 KB Output is correct
6 Correct 48 ms 1592 KB Output is correct
7 Incorrect 0 ms 200 KB Cop can catch the robber, but start() returned -1
8 Halted 0 ms 0 KB -