Mixing
bfs competitve programming [on hold]
up vote
-5
down vote
favorite
Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);
}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);
}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];
}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}
for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");
}
c algorithm
asked yesterday
humblefool
436
put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
up vote
-5
down vote
favorite
Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);
}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);
}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];
}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}
for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");
}
c algorithm
asked yesterday
humblefool
436
put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
1
... and your link doesn't work anyway.
– Jabberwocky
yesterday
add a comment |
up vote
-5
down vote
favorite
up vote
-5
down vote
favorite
Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);
}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);
}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];
}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}
for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");
}
c algorithm
asked yesterday
humblefool
436
Please anyone help me i am new to competitive programming I created my own small test cases , i am getting correct answer in all of them ,And I am passing one test cases of system also,But filing in remaining eleven test cases Please anyone help me
Link for the question
https://hackerrank-challenge-pdfs.s3.amazonaws.com/29036-the-story-of-a-tree-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1542565481&Signature=WoegY4gKUz0OUDEQ3n2UT80FUc0%3D&response-content-disposition=inline%3B%20filename%3Dthe-story-of-a-tree-English.pdf&response-content-type=application%2Fpdf
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
struct queue {
int rear;
int front;
int capacity;
int* array;
};
int visited[100002], parent[100002];
struct queue* createqueue(int capacity) {
struct queue* Q = (struct queue*)malloc(sizeof(struct queue));
Q->capacity = capacity;
Q->front = -1;
Q->rear = -1;
Q->array = (int*)malloc(sizeof(int)*capacity);
return Q;
}
int isempty(struct queue* Q) {
return(Q->front == -1 && Q->rear == -1);
}
int isfull(struct queue* Q) {
return((Q->rear + 1) % Q->capacity == Q->front);
}
void push(struct queue* Q, int data) {
if (isfull(Q))
return;
else if (isempty(Q))
{
Q->rear = 0;
Q->front = 0;
Q->array[Q->rear] = data;
}
else {
Q->rear = ((Q->rear + 1) % Q->capacity);
Q->array[Q->rear] = data;
}
}
int pop(struct queue* Q) {
if (isempty(Q))
return -1;
else if (Q->rear == Q->front) {
int temp = Q->rear;
Q->rear = -1;
Q->front = -1;
return(Q->array[temp]);
}
else {
int temp = Q->front;
Q->front = ((Q->front + 1) % Q->capacity);
return Q->array[temp];
}
}
void bfs(int** graph, int ver, int s) {
struct queue* Q = createqueue(100005);
push(Q, s);
visited[s] = 1;
int v, w;
while (!isempty(Q)) {
v = pop(Q);
for (int j = 0; j < ver; j++) {
if (visited[j] == 0 && graph[v][j] == 1)
{
if (v == j)
continue;
parent[j] = v;
push(Q, j);
visited[j] = 1;
}
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t) {
int** graph;
int i, ver;
scanf("%d", &ver);
graph = (int**)malloc(sizeof(int*)*ver);
for (i = 0; i < ver; i++)
graph[i] = (int*)malloc(sizeof(int)*ver);
for (int i = 0; i < ver; i++) {
for (int j = 0; j < ver; j++) {
graph[i][j] = 0;
}
}
// printf("%d", graph[1][1]);
for (int j = 0; j < ver - 1; j++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u - 1][v - 1] = 1;
graph[v - 1][u - 1] = 1;
}
int g, k;
scanf("%d %d", &g, &k);
int count, win = 0;
int vchild, upar, alice[100002];
for (int i = 0; i < ver; i++)
alice[i] = -1;
for (int i = 0; i < g; i++) {
scanf("%d %d", &upar, &vchild);
alice[vchild - 1] = upar - 1;
}
for (int i = 0; i < ver; i++) {
for (int k = 0; k < ver; k++)
visited[k] = 0;
for (int m = 0; m < ver; m++)
parent[i] = -1;
bfs(graph, ver, i);
count = 0;
for (int j = 0; j < ver; j++) {
if (alice[j] != -1 && alice[j] == parent[j])
count++;
}
if (count >= k)
win++;
}
for (int i = 0; i < ver; i++)
// printf("parent after bfs is %d Alice is %d", parent[i],alice[i]);
// printf("%d", win);
for (int i = 2; i <= win && i <= ver; i++) {
while (win%i == 0 && ver%i == 0) {
win = win / i;
ver = ver / i;
}
}
printf("%d/%dn", win, ver);
t--;
}
system("pause");
}
c algorithm
c algorithm
asked yesterday
humblefool
436
asked yesterday
humblefool
436
asked yesterday
humblefool
436
asked yesterday
humblefool
436
asked yesterday
humblefool
436
436
put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as unclear what you're asking by MrSmith42, Toby Speight, stark, Richardissimo, gnat 12 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
2
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
1
... and your link doesn't work anyway.
– Jabberwocky
yesterday
add a comment |
2
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
1
... and your link doesn't work anyway.
– Jabberwocky
yesterday
2
2
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
1
1
... and your link doesn't work anyway.
– Jabberwocky
yesterday
... and your link doesn't work anyway.
– Jabberwocky
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
Stack Overflow is not a site for solving your competitive programming tasks. If you want to ask here, you need to create a Minimal, Complete, and Verifiable example.
– kfx
yesterday
1
... and your link doesn't work anyway.
– Jabberwocky
yesterday