Page 1 of 7

P-280-Can anyone helped me ?

Posted: Thu Apr 24, 2003 5:47 am
by Red Scorpion
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:

Posted: Tue Apr 29, 2003 10:51 pm
by Per
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)

Posted: Wed Apr 30, 2003 3:31 am
by Red Scorpion
Hi, Thanks per.
I got AC. :lol: :lol: :lol:

280 why TLE?

Posted: Tue May 20, 2003 11:36 pm
by Runtime_Error
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

280(Vertex) Why WA?

Posted: Sun Nov 09, 2003 2:03 am
by yaroslavvb
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]

281 Vertex - Time Limit Exceeded

Posted: Tue Nov 25, 2003 11:50 pm
by screagan
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]

Should be 280 Vertex

Posted: Sat Nov 29, 2003 7:13 am
by screagan
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.

Posted: Tue Dec 23, 2003 2:37 pm
by IBelieve
I also get WA but using Pascal
Can you provide some sample test cases for me ?

280 - Vertex WA

Posted: Sat Jan 17, 2004 12:43 pm
by neno_uci
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.

Problem 280 (Vertex)

Posted: Thu Apr 22, 2004 6:03 pm
by Ferdous
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..........

Re: Problem 216 (Vertex)

Posted: Fri Apr 23, 2004 9:28 am
by CDiMa
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

Posted: Fri Apr 23, 2004 12:27 pm
by Ferdous
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.

Posted: Fri Apr 23, 2004 1:53 pm
by CDiMa
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

Posted: Fri Apr 23, 2004 3:59 pm
by Ferdous
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?

Posted: Fri Apr 23, 2004 4:55 pm
by CDiMa
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