QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#605408	#2644. Cats or Dogs	hztmax0	38	11ms	7196kb	C++17	1.2kb	2024-10-02 17:05:59	2024-10-02 17:06:00

Judging History

你现在查看的是最新测评结果

[2024-10-02 17:06:00]
评测

测评结果：38
用时：11ms
内存：7196kb

查看

[2024-10-02 17:05:59]
提交

answer

#include <iostream>
#include <vector>
#include "catdog.h"

using namespace std;

const int N = 1e5 + 5; 

int n, a[N];
vector<int> e[N];
int f[N][2];

void initialize (int N, vector<int> A, vector<int> B) {
  n = N;
  for (int i = 0; i < n; ++i) {
    e[A[i]].push_back(B[i]);
    e[B[i]].push_back(A[i]);
  }
}

void DP (int u, int r) {
  f[u][0] = f[u][1] = 0;
  for (auto v : e[u]) {
    if (v != r) {
      DP(v, u);
      f[u][0] += min(f[v][0], f[v][1] + 1);
      f[u][1] += min(f[v][1], f[v][0] + 1);
    }
  }
  if (a[u] == 1) f[u][0] = N;
  if (a[u] == 2) f[u][1] = N;
}

int Solve () {
  DP(1, 0);
  return min(f[1][0], f[1][1]);
}

int cat (int v) {
  a[v] = 1; 
  return Solve();
}

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

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

// void Test () {
//   int N;
//   cin >> N;
//   vector<int> A(N), B(N);
//   for (int i = 0; i < N - 1; ++i) {
//     cin >> A[i] >> B[i];
//   }
//   initialize(N, A, B);
//   int Q;
//   cin >> Q;
//   for (int T, v; Q--; ) {
//     cin >> T >> v;
//     cout << (T == 1 ? cat : (T == 2 ? dog : neighbor))(v) << '\n';
//   }
// }

// int main () { Test(); }

源文件, 语言: C++17

详细

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 0ms

memory: 6800kb

input:

output:

result:

ok 75 lines

Test #2:

score: 8

Accepted

time: 2ms

memory: 6444kb

input:

output:

result:

ok 32 lines

Test #3:

score: 8

Accepted

time: 0ms

memory: 6652kb

input:

output:

result:

ok 43 lines

Test #4:

score: 8

Accepted

time: 2ms

memory: 6096kb

input:

output:

result:

ok 100 lines

Test #5:

score: 8

Accepted

time: 2ms

memory: 6424kb

input:

output:

result:

ok 91 lines

Test #6:

score: 8

Accepted

time: 1ms

memory: 6452kb

input:

output:

result:

ok 100 lines

Test #7:

score: 8

Accepted

time: 0ms

memory: 6632kb

input:

output:

result:

ok 100 lines

Test #8:

score: 8

Accepted

time: 2ms

memory: 6880kb

input:

output:

result:

ok 100 lines

Test #9:

score: 8

Accepted

time: 1ms

memory: 6528kb

input:

output:

result:

ok 100 lines

Test #10:

score: 8

Accepted

time: 0ms

memory: 6492kb

input:

output:

result:

ok 100 lines

Test #11:

score: 8

Accepted

time: 0ms

memory: 7196kb

input:

output:

result:

ok 64 lines

Test #12:

score: 8

Accepted

time: 1ms

memory: 6644kb

input:

output:

result:

ok single line: '0'

Test #13:

score: 8

Accepted

time: 0ms

memory: 6152kb

input:

output:

result:

ok 47 lines

Test #14:

score: 8

Accepted

time: 1ms

memory: 6760kb

input:

output:

result:

ok 64 lines

Test #15:

score: 8

Accepted

time: 0ms

memory: 6448kb

input:

output:

result:

ok 55 lines

Test #16:

score: 8

Accepted

time: 1ms

memory: 6180kb

input:

output:

result:

ok 97 lines

Subtask #2:

score: 30

Accepted

Dependency #1:

100%

Accepted

Test #17:

score: 30

Accepted

time: 5ms

memory: 6200kb

input:

output:

result:

ok 747 lines

Test #18:

score: 30

Accepted

time: 3ms

memory: 6364kb

input:

output:

result:

ok 730 lines

Test #19:

score: 30

Accepted

time: 0ms

memory: 6264kb

input:

output:

result:

ok 426 lines

Test #20:

score: 30

Accepted

time: 2ms

memory: 6168kb

input:

output:

result:

ok 20 lines

Test #21:

score: 30

Accepted

time: 0ms

memory: 6580kb

input:

output:

result:

ok 387 lines

Test #22:

score: 30

Accepted

time: 3ms

memory: 6848kb

input:

output:

result:

ok 406 lines

Test #23:

score: 30

Accepted

time: 7ms

memory: 6204kb

input:

output:

result:

ok 962 lines

Test #24:

score: 30

Accepted

time: 6ms

memory: 6700kb

input:

output:

result:

ok 838 lines

Test #25:

score: 30

Accepted

time: 3ms

memory: 6740kb

input:

output:

result:

ok 753 lines

Test #26:

score: 30

Accepted

time: 2ms

memory: 6684kb

input:

output:

result:

ok 294 lines

Test #27:

score: 30

Accepted

time: 0ms

memory: 7032kb

input:

output:

result:

ok 300 lines

Test #28:

score: 30

Accepted

time: 0ms

memory: 6872kb

input:

output:

result:

ok 184 lines

Test #29:

score: 30

Accepted

time: 11ms

memory: 6324kb

input:

output:

result:

ok 1000 lines

Test #30:

score: 30

Accepted

time: 0ms

memory: 6804kb

input:

output:

result:

ok 561 lines

Test #31:

score: 30

Accepted

time: 0ms

memory: 6656kb

input:

output:

result:

ok 94 lines

Test #32:

score: 30

Accepted

time: 2ms

memory: 6652kb

input:

output:

result:

ok 703 lines

Subtask #3:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #33:

score: 0

Time Limit Exceeded

input:

50516
80 25781
27578 39138
42128 34705
31858 9513
10874 47059
13846 22138
6315 27891
44827 23006
44544 26597
9205 1572
3857 18166
28675 43775
6486 15805
23949 32263
42848 17311
21484 155
27144 42220
30798 6582
3641 36355
1695 8694
15029 38762
38309 25196
45604 11904
13989 4290
39713 48125
36823 9220...