oj.uz

Submission #857497

# Submission time Handle Problem Language Result Execution time Memory
857497 2023-10-06T09:58:10 Z Abito Cats or Dogs (JOI18_catdog) C++17
8 / 100
 165 ms 436 KB 
#include "catdog.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=20;
int n,a[N];
bool b[N][N],vis[N];
pair<int,int> e[N];
vector<int> adj[N];
bool dfs(int node){
    if (a[node]==2) return 0;
    vis[node]=true;
    bool ans=true;
    for (auto u:adj[node]){
        if (vis[u] || b[u][node]) continue;
        ans&=dfs(u);
    }return ans;
}
int getans(){
    int ans=n;
    for (int i=0;i<(1<<(n-1));i++){
        int g=__popcount(i);
        for (int j=0;j<n-1;j++) b[e[j].F][e[j].S]=b[e[j].S][e[j].F]=bool(i&(1<<j));
        memset(vis,0,sizeof(vis));
        for (int j=1;j<=n;j++){
            if (a[j]!=1 || vis[j]) continue;
            bool x=dfs(j);
            if (!x) g=n;
        }ans=min(ans,g);
    }return ans;
}
void initialize(int NN, std::vector<int> A, std::vector<int> B) {
    n=NN;
    for (int i=0;i<n-1;i++){
        adj[A[i]].pb(B[i]);
        adj[B[i]].pb(A[i]);
        e[i]={A[i],B[i]};
    }return;
}
int cat(int v){
  a[v]=1;
  return getans();
}

int dog(int v) {
  a[v]=2;
  return getans();
}

int neighbor(int v) {
  a[v]=0;
  return getans();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 45 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 112 ms 348 KB Output is correct
7 Correct 165 ms 348 KB Output is correct
8 Correct 121 ms 408 KB Output is correct
9 Correct 134 ms 344 KB Output is correct
10 Correct 112 ms 408 KB Output is correct
11 Correct 67 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 77 ms 412 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 45 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 112 ms 348 KB Output is correct
7 Correct 165 ms 348 KB Output is correct
8 Correct 121 ms 408 KB Output is correct
9 Correct 134 ms 344 KB Output is correct
10 Correct 112 ms 408 KB Output is correct
11 Correct 67 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 77 ms 412 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 45 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 112 ms 348 KB Output is correct
7 Correct 165 ms 348 KB Output is correct
8 Correct 121 ms 408 KB Output is correct
9 Correct 134 ms 344 KB Output is correct
10 Correct 112 ms 408 KB Output is correct
11 Correct 67 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 77 ms 412 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -