10600 - ACM Contest and Blackout

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

Moderator: Board moderators

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

10600 why WA TT-TT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Post by sds1100 » Sun Mar 12, 2006 4:34 pm

I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code: Select all

code cut
I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Post by tmdrbs6584 » Sat Mar 25, 2006 2:26 am

Code: Select all

좋냐 심성일

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Mar 25, 2006 12:16 pm

This is a public forum, so please post in English.

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

10600 Why WA ?

Post by sumantbhardvaj » Tue Apr 10, 2007 10:16 pm

I tried to implement the algorithm mentioned in cormen for finding the second best minimum spanning tree . (along with prims to find minimum spanning tree ) but it is giving wrong answer in 0.029 secs.. :cry: :cry:

some body plz provide me with some test cases or have a look at my code.. :( :( :(

Code: Select all


code removed after ACC
Last edited by sumantbhardvaj on Mon Apr 16, 2007 5:58 pm, edited 2 times in total.

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:

Post by sumantbhardvaj » Mon Apr 16, 2007 2:46 pm

got ACC :) :)

changed it from PRIMS to Kruskal ..

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Apr 16, 2007 3:38 pm

remove your code, then

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Mon Jul 30, 2007 4:52 pm

Hi, I am getting WA for this problem, but my code is right for the inputs.

Code: Select all

#include <stdio.h>

#define INF 2100100100
#define MAXVERTICES 500
#define MAXARESTAS MAXVERTICES * MAXVERTICES

typedef struct
{
    int u, v, c;
}
Aresta;

typedef enum
{
    FALSE = 0, TRUE
}
boolean;

int pai[MAXVERTICES], rank[MAXVERTICES];
Aresta aresta[MAXARESTAS];
boolean flag[MAXARESTAS];

int arestas, vertices;

void MakeSet(int x);
int FindSet(int x);
void Union(int x, int y);

int cmp(Aresta *a, Aresta *b);

int kruskal(int retira);

int main(int argc, char **argv)
{
    int casos;

    scanf(" %d", &casos);

    while (casos--)
    {
        int i, ArvGeradora = 0, SegundaArv = INF;

        scanf(" %d %d", &vertices, &arestas);

        for (i = 1; i <= arestas; i++)
        {
            int u, v, c;

            flag[i] = FALSE;
            MakeSet(i);

            scanf(" %d %d %d", &u, &v, &c);

            aresta[i].u = u;
            aresta[i].v = v;
            aresta[i].c = c;
        }

        qsort(aresta, arestas + 1, sizeof(Aresta), cmp);

        for (i = 1; i <= arestas; i++)
        {}

        for (i = 1; i <= arestas; i++)
        {
            if (FindSet(aresta[i].u) != FindSet(aresta[i].v))
            {
                Union(aresta[i].u, aresta[i].v);

                ArvGeradora += aresta[i].c;
                flag[i] = TRUE;
            }
        }

        for (i = 1; i <= arestas; i++)
        {
            int j;

            for (j = 1; j <= arestas; j++)
            {
                MakeSet(j);
            }

            if (flag[i])
            {
                int temp = kruskal(i);

                if (temp < SegundaArv)
                {
                    SegundaArv = temp;
                }
            }
        }

        printf("%d %d\n", ArvGeradora, SegundaArv);
    }

    return 0;
}

void MakeSet(int x)
{
    pai[x] = x;
    rank[x] = 1;
}

int FindSet(int x)
{
    if (x != pai[x])
    {
        pai[x] = FindSet(pai[x]);
    }

    return pai[x];
}

void Union(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);

    if (rank[x] > rank[y])
    {
        pai[y] = x;
        rank[x] += rank[y];
    }

    else
    {
        pai[x] = y;
        rank[y] += rank[x];
    }
}

int cmp(Aresta *a, Aresta *b)
{
    return a->c - b->c;
}

int kruskal(int retira)
{
    int i, somaPesos = 0, cont = 0;

    for (i = 1; i <= arestas; i++)
    {
        if (FindSet(aresta[i].u) != FindSet(aresta[i].v) && i != retira)
        {
            Union(aresta[i].u, aresta[i].v);

            somaPesos += aresta[i].c;
            cont++;
        }
    }

    if (cont >= (vertices - 1))
    {
        return somaPesos;
    }

    else
    {
        return INF;
    }
}
Thanks.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Got TLE

Post by mohsincsedu » Sun Dec 23, 2007 12:00 am

After TLE....

I got WA....


need some io..



here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>


#define INF 10000

typedef struct st
{
	int weight;
	int v1,v2;
}edges;

st e[305],sav[305];
int nver,nedges,u[105],v[105],used[105],uused[105];
char intree[500];


int Min(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}


int compare(const void* a, const void* b)
{
	edges *a1, *b1;
	a1 = (edges*)a; b1 = (edges*)b;
	if (a1[0].weight > b1[0].weight)
		return 1;
	return -1;
}

int istreedone()
{
	int ii; 
	char c = intree[0];
	for (ii=0;ii<nver;ii++)
		if (intree[ii] == 0)
			return 0;
	for (ii=1;ii<nver;ii++)
		if (intree[ii] != c)
			return 0;
	return 1;
}

int kruskal()
{
	int ii,jj,color,cur,toconvert,index;
	int total;
	qsort(e,nedges,sizeof(edges),compare);
	for (ii=0;ii<nver;ii++)
	{
		intree[ii] = 0;
		used[ii] = 0;
	}
	ii = 0; color = 1; total = 0,index = 0;
	while (istreedone()==0)
	{
		if (intree[e[ii].v1]!=intree[e[ii].v2])
		{
			if (intree[e[ii].v1] > intree[e[ii].v2])
			{
				cur = intree[e[ii].v1]; toconvert = e[ii].v2;
			}
			else
			{
				cur = intree[e[ii].v2]; toconvert = e[ii].v1;
			}
			total += e[ii].weight;
			/*u[index] = e[ii].v1;
			v[index] = e[ii].v2;
			index++;*/
			used[ii] = 1;
			if (intree[toconvert] == 0)
			{
				intree[toconvert] = cur;
			}
			else
			{
				toconvert = intree[toconvert];
				for (jj=0;jj<nver;jj++)
					if (intree[jj] == toconvert)
						intree[jj] = cur;
			}
		}
		else
		{
			if (intree[e[ii].v1]==0 && intree[e[ii].v2] == 0){
				intree[e[ii].v1] = color;
				intree[e[ii].v2] = color;
				total+= e[ii].weight;
				/*u[index] = e[ii].v1;
				v[index] = e[ii].v2;
				index++;*/
				used[ii] = 1;
				color++;
			}
		}
		ii++;
	}
	return total;
}


int main()
{
	int nCase,i,min,cost,temp,j;
	//freopen("kruskal.in","r",stdin);
	scanf("%d",&nCase);


	while(nCase--)
	{
		scanf("%d %d",&nver,&nedges);
		for(i = 0;i<nedges;i++)
		{
			scanf("%d %d %d",&e[i].v1,&e[i].v2,&e[i].weight);
			e[i].v1--;
			e[i].v2--;
		}
		cost = kruskal();
		min = INF;
		for(i = 0;i<nedges;i++)
			uused[i] = used[i];
		
		for(i = 0;i<nedges;i++)
		{
			if(uused[i])
			{
				for(j = 0;j<nedges;j++)
				{
					sav[j].v1 = e[j].v1;
					sav[j].v2 = e[j].v2;
					sav[j].weight = e[j].weight;
				}
				
				e[i].weight = INF;
				temp = kruskal();
				
				min = Min(min,temp);
				for(j = 0;j<nedges;j++)
				{
					e[j].v1 = sav[j].v1;
					e[j].v2 =  sav[j].v2;
					e[j].weight = sav[j].weight;
				}
				
			}
		}
		
		if(cost>min||min==INF)
			min = cost;
		printf("%d %d\n",cost,min);
		
		
	}



	
	return 0;
}
Thanks in advanced...
Amra korbo joy akhdin............................

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Sun Dec 23, 2007 5:39 pm

what is the output of the following input?
1
2 1
1 2 3

I think the output should be: 3 3

is it ok??
Amra korbo joy akhdin............................

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

10600 - ACM Contest and Blackout

Post by mmfrb » Wed Sep 19, 2012 2:12 am

Why WA?

Code: Select all

AC
Last edited by mmfrb on Sat Sep 22, 2012 4:58 pm, edited 1 time in total.

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Re: 10600 - ACM Contest and Blackout

Post by mmfrb » Wed Sep 19, 2012 6:48 pm

No one? Please? I dunno what I can change anymore.. :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10600 - ACM Contest and Blackout

Post by brianfry713 » Thu Sep 20, 2012 8:59 pm

Input:

Code: Select all

1
33 89
1 11 236
1 29 209
1 32 53
2 10 43
2 4 142
2 9 148
3 19 148
3 30 80
3 4 243
4 12 201
5 20 253
6 24 126
6 33 86
6 4 51
7 11 117
7 11 290
7 26 158
7 31 270
7 32 11
7 32 119
8 20 199
8 33 209
8 5 74
9 16 64
9 18 119
9 20 44
10 28 145
11 12 198
11 17 36
11 18 100
12 32 235
12 6 297
12 7 127
12 7 90
13 16 153
14 26 76
15 23 95
15 5 92
16 10 143
16 6 125
17 24 100
17 5 173
18 25 265
18 31 234
18 8 292
19 10 43
19 29 220
20 25 228
20 3 222
20 32 227
21 17 84
21 22 133
21 23 18
22 20 25
22 26 85
23 14 264
23 4 128
23 5 124
24 4 100
24 6 209
24 8 16
25 26 25
25 9 205
26 12 104
26 13 166
27 16 37
27 20 179
28 11 286
28 11 36
28 11 5
28 16 212
28 27 107
28 29 255
29 27 218
29 9 180
30 10 108
30 10 211
30 18 171
30 26 33
31 10 187
31 12 167
31 18 296
31 32 183
31 9 171
32 25 218
32 25 276
32 25 80
33 16 53
33 5 173
AC output:

Code: Select all

2207 2211
Check input and AC output for thousands of problems on uDebug!

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Re: 10600 - ACM Contest and Blackout

Post by mmfrb » Thu Sep 20, 2012 11:08 pm

Yes! Your sample input made me think that the number of disjoint sets before and after has to be the same! Now i got AC... thanks so so so much!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10600 - ACM Contest and Blackout

Post by brianfry713 » Thu Oct 25, 2012 11:12 pm

Input:

Code: Select all

1
47 102
44 46 262
21 11 190
42 44 27
2 27 121
4 15 193
17 30 246
7 8 287
1 29 244
19 8 196
33 2 42
11 40 191
47 23 36
43 27 268
22 27 139
36 34 127
44 26 136
5 41 202
33 11 99
20 11 169
21 17 1
14 37 31
36 6 236
41 22 35
47 6 154
33 18 250
12 33 117
31 17 13
20 34 184
30 25 155
25 39 132
40 39 223
24 1 140
46 36 268
4 18 191
21 22 224
32 41 259
2 9 46
35 7 171
39 37 29
30 19 115
47 21 170
1 36 188
15 18 101
32 41 227
7 16 156
26 3 16
34 26 240
19 12 183
8 16 243
5 29 39
25 44 119
39 5 71
10 15 25
29 23 68
24 34 157
5 24 138
30 20 283
41 21 200
36 10 124
43 16 262
18 31 144
1 45 98
15 38 209
37 24 250
3 41 59
26 44 262
45 24 166
45 17 168
7 27 244
2 24 121
11 5 162
34 10 92
3 32 296
26 43 24
45 35 208
41 3 50
44 22 217
13 2 102
18 2 186
21 37 163
25 46 72
13 26 31
23 6 162
18 26 241
5 36 231
7 1 93
28 39 15
9 6 229
10 43 86
26 39 10
24 16 209
2 28 31
33 27 173
12 27 243
47 32 296
27 34 36
18 29 130
2 47 37
44 8 134
14 34 260
8 33 38
36 14 281
AC output:

Code: Select all

3956 3958
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 10600 - ACM Contest and Blackout

Post by afruizc » Wed Dec 12, 2012 9:46 am

I have solved this problem, but I'm getting RTE.
I've used the next procedure:
For the first MST, simply run kruskal and print the MST value, also every time an edge is added to the Tree, I add it to a vector to keep track of it later. After this process, I take every one of the edges, I flag the edge being processed and I run MST ignoring the flagged edge. Then, among all the MST I pick the least one.
Here is my code.
After some debugging and thanks to the help of Brianfry713, I've found that the exception is trown un line 57 when processing the previous I/O, with a value of j=7 and w = 128.

Here is my code:

Code: Select all

Didn't really know what was wrong....
I'd really appreciate any help that could be given to me :D
Last edited by afruizc on Tue Jan 08, 2013 2:33 am, edited 1 time in total.

Post Reply

Return to “Volume 106 (10600-10699)”