Tasks Details
hard
1.
PetsAndToys
Each of N people has either a dog or a cat, and owns a toy for dog or for cat. Is it possible to exchange toys between acquaintances so that every animal gets an appropriate toy?
Task Score
100%
Correctness
100%
Performance
100%
During an Animal Day event, N people (numbered from 0 to N−1) showed up. Each of them had either a dog or a cat. The organizers decided to give them a wonderful gift: a toy for each animal.
After the event, it turned out that some people who owned a dog had received a cat-toy, and some people who owned a cat received a dog-toy. People may exchange toys, but only if they know each other (otherwise they have no way to contact the other person). The pair of people can exchange toys multiple times.
Knowing who knows who, who owns which animal, and what kind of toy he or she received, can you determine whether it is possible for people to exchange toys in such a way that every dog ends up with a dog-toy and every cat gets a cat-toy?
Write a function:
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B);
that returns true if it is possible to exchange toys in such a way that every animal receives an appropriate toy, or false otherwise. First two arrays describe the pets (array P) and toys (array T) that every person owns. The J-th person owns pet P[J] and toy T[J] (1 means dog or dog-toy and 2 means cat or cat-toy). The next two arrays, A and B, both of length M, describe the relationships between people. For each integer K from 0 to M−1, person A[K] knows person B[K].
Examples:
1. Given:
P = [1, 1, 2] T = [2, 1, 1] A = [0, 2] B = [1, 1]the function should return true. Person 0 can exchange toys with person 1 to obtain a dog-toy, and then person 1 can exchange toys with person 2.
2. Given:
P = [2, 2, 1, 1, 1] T = [1, 1, 1, 2, 2] A = [0, 1, 2, 3] B = [1, 2, 0, 4]the function should return false. There is no way for persons 3 and 4 to exchange toys with others.
3. Given:
P = [1, 1, 2, 2, 1, 1, 2, 2] T = [1, 1, 1, 1, 2, 2, 2, 2] A = [0, 2, 4, 6] B = [1, 3, 5, 7]the function should return false. There is no way for persons 2 and 3 and for persons 4 and 5 to exchange toys with others.
4. Given:
P = [2, 2, 2, 2, 1, 1, 1, 1] T = [1, 1, 1, 1, 2, 2, 2, 2] A = [0, 1, 2, 3, 4, 5, 6] B = [1, 2, 3, 4, 5, 6, 7]the function should return true.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [0..200,000];
- each element of arrays P and T is an integer that can have one of the following values: 1, 2;
- each element of arrays A and B is an integer within the range [0..N-1];
- for each integer K from 0 to M−1, elements A[K] and B[K] are different;
- there are no redundant elements in arrays A, B; more formally every unordered pair of persons a, b will appear as A[K], B[K] for at most one K.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 6 minutes
Notes
not defined yet
Code: 04:58:03 UTC,
java,
autosave
Code: 04:58:04 UTC,
java,
autosave
Code: 04:58:14 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n =
}
Code: 04:58:45 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
Code: 04:59:16 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
que
}
}
Code: 04:59:27 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
queue<int> q;
q.push()
}
}
Code: 04:59:58 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
dog_toy += T
}
}
Code: 05:00:22 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
dog_toy += T[i] == 1;
cat += P[i] == 2;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u =
}
}
}
Code: 05:00:50 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
dog_toy += T[i] == 1;
cat += P[i] == 2;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog
}
}
}
}
Code: 05:01:21 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
}
}
}
}
Code: 05:01:36 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
u.push()
}
}
}
}
Code: 05:01:46 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
u.push()
}
}
}
}
Code: 05:02:04 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
u.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
Compile error
func.cpp: In function 'bool solution(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
func.cpp:20:9: error: 'queue' was not declared in this scope
queue<int> q;
^~~~~
func.cpp:20:15: error: expected primary-expression before 'int'
queue<int> q;
^~~
func.cpp:21:9: error: 'q' was not declared in this scope
q.push(i);
^
func.cpp:35:19: error: request for member 'push' in 'u', which is of non-class type 'int'
u.push(v);
^~~~
Code: 05:02:15 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
u.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
Compile error
func.cpp: In function 'bool solution(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
func.cpp:36:19: error: request for member 'push' in 'u', which is of non-class type 'int'
u.push(v);
^~~~
Code: 05:02:18 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Code: 05:02:18 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
expand all
Example tests
1.
5.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 5.000 sec.
1.
4.120 s
RUNTIME ERROR,
tested program terminated with exit code 134
stderr:
terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
1.
5.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 5.000 sec.
1.
4.736 s
RUNTIME ERROR,
tested program terminated with exit code 134
stderr:
terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
Code: 05:02:45 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got False expected True
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
WRONG ANSWER,
got False expected True
Code: 05:03:01 UTC,
cpp,
autosave
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
// dog += P[i] == 1;
// cat += P[i] == 2;
// dog_toy += T[i] == 1;
// cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Code: 05:03:02 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
// dog += P[i] == 1;
// cat += P[i] == 2;
// dog_toy += T[i] == 1;
// cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
Code: 05:03:15 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
visited[i] = true;
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
Code: 05:03:26 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
visited[i] = true;
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis
Code: 05:03:30 UTC,
cpp,
final,
score:
100
// you can use includes, for example:
// #include <algorithm>
#include <queue>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
bool solution(vector<int> &P, vector<int> &T, vector<int> &A, vector<int> &B) {
// write your code in C++14 (g++ 6.2.0)
int n = P.size(), m = A.size();
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<bool> visited(n);
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int dog = 0, dog_toy = 0, cat = 0, cat_toy = 0;
queue<int> q;
q.push(i);
visited[i] = true;
dog += P[i] == 1;
cat += P[i] == 2;
dog_toy += T[i] == 1;
cat_toy += T[i] == 2;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (visited[v]) continue;
visited[v] = true;
dog += P[v] == 1;
cat += P[v] == 2;
dog_toy += T[v] == 1;
cat_toy += T[v] == 2;
q.push(v);
}
}
if (cat != cat_toy || dog != dog_toy) return false;
}
return true;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N+M)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
5.
0.001 s
OK
6.
0.001 s
OK
expand all
Performance tests
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.012 s
OK
4.
0.012 s
OK
5.
0.012 s
OK
1.
0.080 s
OK
2.
0.068 s
OK
3.
0.084 s
OK
4.
0.076 s
OK
1.
0.048 s
OK
2.
0.044 s
OK
3.
0.048 s
OK
4.
0.044 s
OK
1.
0.080 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
4.
0.072 s
OK