280 - Vertex

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

P-280-Can anyone helped me ?

Post by Red Scorpion » Thu Apr 24, 2003 5:47 am

Can anyone tell me what output for this test case:

input:
100
1 2 3 4 5 6 7 8 9 10 11 100 14 44 25 28 0
2 1 4 6 8 9 10 44 25 0
3 2 1 4 6 8 9 33 11 100 0
4 2 1 0
0
10 1 2 3 4 5 6 7 8 9 10
10
1 10 0
0
2 1 2
0

Thanks. :lol: :lol:

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Apr 29, 2003 10:51 pm

My solution outputs:

Code: Select all

83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
9 1 2 3 4 5 6 7 8 9
10 1 2 3 4 5 6 7 8 9 10
(10 lines)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Apr 30, 2003 3:31 am

Hi, Thanks per.
I got AC. :lol: :lol: :lol:

Runtime_Error
New poster
Posts: 5
Joined: Sat Oct 05, 2002 8:01 pm
Location: Yerevan, Armenia
Contact:

280 why TLE?

Post by Runtime_Error » Tue May 20, 2003 11:36 pm

why do i got TLE??

[cpp]
#include <iostream.h>
#include <queue>

using std::queue;

void main()
{
int a[110][110], i, j, n, p, q, inNum, nNum, fr;
bool in[110];
while (1) {
cin >> n;
if (n == 0)
break;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[j] = 0;
while (1) {
cin >> p;
if (p == 0)
break;
while (1) {
cin >> q;
if (q == 0)
break;
a[p - 1][q - 1] = 1;
}
}
cin >> nNum;
for (i = 0; i < nNum; i++) {
queue<int> Q;
cin >> p;
inNum = 0;
for (j = 0; j < n; j++)
in[j] = false;

for (j = 0; j < n; j++)
if (a[p - 1][j] == 1)
Q.push(j);

while (!Q.empty()) {
fr = Q.front();
Q.pop();
in[fr] = true;
for (j = 0; j < n; j++)
if (!in[j] && (a[fr][j] == 1))
Q.push(j);
}
for (j = 0; j < n; j++)
if (!in[j])
inNum++;
cout << inNum << ' ';
for (j = 0; j < n; j++)
if (!in[j]) {
cout << j + 1;
if (j != n - 1)
cout << ' ';
}
cout << endl;
}
}
}
[/cpp]
:cry: :x
A Runtime Error Has Occured, Do You Wish To Debug?

yaroslavvb
New poster
Posts: 1
Joined: Sun Nov 09, 2003 1:50 am
Location: Corvallis, OR
Contact:

280(Vertex) Why WA?

Post by yaroslavvb » Sun Nov 09, 2003 2:03 am

I'm getting WA using Java, I got correct answer for provided input, and for test cases posted in this board :(

This is the code:

[java]
import java.io.*;
import java.util.*;

class Main {
public static void main(String argv[]) throws Exception {
Main prog = new Main();
prog.run();
}

public void run() throws Exception {
String line;
while ((line = ReadLn(2550))!=null) {
// read graph:
int vertex_total = Integer.parseInt(line.trim());
if (vertex_total == 0) break;
boolean[][] graph = new boolean[vertex_total][];

// read each vertex spec until hit 0
while (true) {
line = ReadLn(2550);
if ("0".equals(line.trim()))
break;
StringTokenizer str_tok = new StringTokenizer(line);
int vert = Integer.parseInt(str_tok.nextToken())-1;
graph[vert] = new boolean[vertex_total];
initArr(graph[vert]);
try {
while (true) {
int connect = Integer.parseInt(str_tok.nextToken())-1;
if (connect == -1) break;
graph[vert][connect] = true;
}
} catch (NoSuchElementException e) {
System.out.println("Line was "+line);
}
}

// read the query spec
String query = ReadLn(255);
StringTokenizer str_tok = new StringTokenizer(query);
int num_queries = Integer.parseInt(str_tok.nextToken());
for (int i = 0; i < num_queries; ++i) {
int qnode = Integer.parseInt(str_tok.nextToken());
// System.out.println("solving for "+(qnode-1));
solve (graph, qnode-1);
}
}
}

public void solve(boolean[][] graph, int query) {
boolean[] access = new boolean[graph.length];
initArr(access);
access[query] = true;
boolean[] access2 = new boolean[graph.length];
initArr(access2);
for (int stage = 0; stage < access.length; ++stage) {
for (int i = 0; i < access.length; ++i) {
if (!access) continue;
OR(access, graph);
OR(access2, graph);
}
}
printAnswer(access2);
}

public void printAnswer(boolean[] access) {
// count failures
int count = 0;
for (int i = 0; i < access.length; ++i) {
if (access == false)
++count;
}

// print answer
boolean is_first = true;
System.out.print(count+" ");
for (int i = 0; i < access.length; ++i) {
if (access) continue;
if (is_first)
is_first = false;
else
System.out.print(" ");
System.out.print(""+(i+1));
}
System.out.print("\n");
}

public void initArr(boolean[] b) {
for (int i = 0; i < b.length; ++i)
b = false;
}

public void OR(boolean[] b1, boolean[] b2) {
if (b1 == null || b2 == null) return;
for (int i = 0; i < b1.length; ++i)
b1 = b1||b2;
}


static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
}[/java]

screagan
New poster
Posts: 2
Joined: Tue Nov 25, 2003 11:41 pm

281 Vertex - Time Limit Exceeded

Post by screagan » Tue Nov 25, 2003 11:50 pm

Hi, surely a depth first search of 100 nodes wouldn't time out, so any ideas what I am doing wrong? Am I reading the input from the judge in an incorrect way that causes my program to constantly wait for some non-existent input? I just can't figure it out :(.

[cpp]

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

streambuf* cinbuf = cin.rdbuf();
streambuf* coutbuf = cout.rdbuf();

void dfs_visit(vector<vector<int> >& G, vector<string>& color, int u)
{
color = "gray";
vector<int>& adj = G;
for (int i=0; i<adj.size(); i++) {
int v = adj;
if (color[v] == "white") {
dfs_visit(G, color, v);
}
}
color = "black";
}

void dfs_sweep(vector<vector<int> >& G, vector<string>& color, vector<int> vertices)
{
fill(color.begin(), color.end(), "white");

for (int i=0; i<vertices.size(); i++) {
int u = vertices;
if (color == "white") {
dfs_visit(G, color, u);
}
}
}

void main()
{
#ifndef ONLINE_JUDGE
ifstream in("Vertex.in");
cin.rdbuf(in.rdbuf());
ofstream out("Vertex.out");
cout.rdbuf(out.rdbuf());
#endif

int n;
cin >> n;
while (true) {
//form the adjacency list
vector<vector<int> > graph(n+1); //n is the number of nodes (numbered consecutively: 1... n)
vector<string> color(n+1);

int node;
while (cin >> node) {
if (node == 0)
break; // no more nodes

int adj_node;
while (cin >> adj_node) {
if (adj_node == 0)
break; //no more adjacent vertices
graph[node].push_back(adj_node);
}
}

int i,j,k;
cin >> j; //number of start nodes to test out
for (i=0; i<j; i++) {
int start;
cin >> start;

//now search the graph starting at "start"
dfs_sweep(graph, color, graph[start]);

//output the results
cout << count(color.begin()+1, color.end(), "white") << " ";
for (k=1; k<color.size(); k++)
if (color[k] == "white")
cout << k << " ";
cout << endl;
}
cin >> n;
if (n == 0) {
break; //no more input
}
}

//restore standard input/output
cin.rdbuf(cinbuf);
cout.rdbuf(coutbuf);
}

[/cpp]

screagan
New poster
Posts: 2
Joined: Tue Nov 25, 2003 11:41 pm

Should be 280 Vertex

Post by screagan » Sat Nov 29, 2003 7:13 am

Sorry guys, I just realized I typed the wrong problem number. Of course, it should be 280 not 281. So, does anyone have any idea why I am receiving the time limit error? It is driving me CRAZY because I just can't figure it out. It would be so great if we could actually get some feedback from our submissions.

IBelieve
New poster
Posts: 14
Joined: Sun Nov 16, 2003 7:40 pm

Post by IBelieve » Tue Dec 23, 2003 2:37 pm

I also get WA but using Pascal
Can you provide some sample test cases for me ?
When people agree with me I always feel that I must be wrong.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

280 - Vertex WA

Post by neno_uci » Sat Jan 17, 2004 12:43 pm

Hello...!!!

I am trying to solve this problem but I always get WA. This is my code:[cpp]
#include <stdio.h>
#define MAX 200

void dfs(int);

int mat[MAX][MAX], tom[MAX], que[MAX], ini, fin, n, t;

int main()
{
scanf("%d", &n);

while (n) {

for (int i = 1; i <= n; i++)
mat[0] = 0;

while (1) {

scanf("%d", &ini);

if (!ini) break;

while (1) {

scanf("%d", &fin);

if (!fin) break;

mat[ini][++mat[ini][0]] = fin;
}

}

scanf("%d", &ini);

for (int i = 0; i < ini; i++)
scanf("%d", &que);

for (int i = 0; i < ini; i++) {

t = n;

for (int j = 1; j <= n; j++)
tom[j] = 0;

dfs(que);

printf("%d", t);

for (int j = 1; j <= n; j++)
if (!tom[j])
printf(" %d", j);

printf("\n");
}

scanf("%d", &n);
}

return 0;
}

void dfs(int inicio)
{
for (int x = 1; x <= mat[inicio][0]; x++)
if (!tom[mat[inicio][x]]) {

tom[mat[inicio][x]] = 1;
dfs(mat[inicio][x]);
t--;
}
}
[/cpp]

Could anyone help me please?
Thanks in advance.
El Neno de la UCI.

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Problem 280 (Vertex)

Post by Ferdous » Thu Apr 22, 2004 6:03 pm

I can't figure out why I am getting RTE. I spent hours together to find out the fault but failed because of my inefficiency in programming :oops: . But I know there are many efficient programmers all over the world who can help me in this regard and I am waiting for help from anyone of you. Please help me. Here's my code:

................Code is deleted later..........
Last edited by Ferdous on Tue May 18, 2004 1:40 pm, edited 2 times in total.
I am destined to live on this cruel world........

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: Problem 216 (Vertex)

Post by CDiMa » Fri Apr 23, 2004 9:28 am

Ferdous wrote:I can't figure out why I am getting RTE. I spent hours together to find out the fault but failed because of my inefficiency in programming :oops: . But I know there are many efficient programmers all over the world who can help me in this regard and I am waiting for help from anyone of you. Please help me. Here's my code:
Hmmm...
Problem 216 is getting in line, while vertex is problem 280.

If you submit code for problem 280 to the judge for problem 216 you may get in input numbers up to 150. This will pass the bounds for your array and produce an RTE.

If you only mistyped the topic then let me know.

Ciao!!!

Claudio

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Post by Ferdous » Fri Apr 23, 2004 12:27 pm

I am extremely sorry for my mistake. I mistyped 216 instead of 280. I sent the code with Problem ID 280 and awarded RTE and still can't figure out what's wrong with my code.
I am destined to live on this cruel world........

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Fri Apr 23, 2004 1:53 pm

Ferdous wrote:I am extremely sorry for my mistake. I mistyped 216 instead of 280. I sent the code with Problem ID 280 and awarded RTE and still can't figure out what's wrong with my code.
The size of the temp array is 100 while a query about 40 nodes will easily overflow that.

Ciao!!!

Claudio

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Post by Ferdous » Fri Apr 23, 2004 3:59 pm

Thank u very much. I got AC just increasing the size of temp array to 1000. But I noticed one thing. My code took more than 0:05.00 time. But others solved it within 0:01.00 time. How can I enhance my code or algorithm so that I can get a better solution?
I am destined to live on this cruel world........

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Fri Apr 23, 2004 4:55 pm

Ferdous wrote:Thank u very much. I got AC just increasing the size of temp array to 1000. But I noticed one thing. My code took more than 0:05.00 time. But others solved it within 0:01.00 time. How can I enhance my code or algorithm so that I can get a better solution?
Probably I'm the best on the board to ask this 8)
In your prog you visit the graph for each node queried. This leads to revisit most of the graph each time.
If you avoid it your prog will be faster...

Ciao!!!

Claudio

Post Reply

Return to “Volume 2 (200-299)”