My program passes all tests created by me, so I don't know what could be the problem with it

subj.
answer please

I tried test 1 given in task on my computer and got the same answer. But i get WA #1 wwhen submit

* Clarification in problem statements: For any pair of crossroads no two segments of the same category connect these crossroads.
* Tests not satisfing this condition are corrected.
* The first test is changed to the sample from the problem statements.
* New time limit is 2.5 seconds (old time limit was 3 seconds).
* New memory limit is 64 MB (old memory limit was 16 MB).
* New tests are added

All solutions are rejudged. More than 100 authors lost AC during this rejudge.

If you got TLE, try change adjacency matrix to edge list.

Of course, with a little optimizations :)

I sort the the 2^k states by the bits it contains, then check the states in order, and always TLE #22

Then, I choose a state randomly in the 2^k states and check if it's legal, and get accepted……

part of my code:

 63     int ans = (1 << k) - 1;
 64     int tot = 1 << k;
 65     int times = 0;
 66     while (tot > 0 && (times * realm < (500000000))) {
 67         int now = rand() % tot;
 68         if (countBit(arr[now]) < countBit(ans)){
 69             memset(visit,0,sizeof(visit));
 70             times++;
 71             if (dfs(0,arr[now])) {
 72                 ans = arr[now];
 73             }
 74         }
 75         arr[now] = arr[--tot];
 76     }

need some test plz. no idea whats wrong. thanks.

I have AC with time 0.953sec, but my solution runs >2sec on a test generated by the following program:

#include <cstdio>
int main(){
    int k = 20;
    int n = 30;
    int m = k+k*(((n-k)*(n-k-1))/2);
    printf("%d %d %d\n",k,n,m);
    for (int i = 1; i <= k; i++){
        printf("%d %d %d\n",i,i+1,i-1);
    }
    for (int i = k+1; i < n; i++){
        for (int j = i+1; j < n; j++){
            for (int l = 0; l < k; l++){
                printf("%d %d %d\n",i,j,l);
            }
        }
        for (int l = 0; l < k; l++){
            printf("%d %d %d\n",i,0,l);
        }
    }
    return 0;
}

Give me some tests or write if there are some sly tests.
I solve this problem by 2^K*N*N.

I am trying to take all possible combinations of k and run union-find to check if 0-1 are connected in that combinations. complexity is O(M(2^K)). is there a faster approach?

Edited by author 16.08.2008 01:01

K==20 at test #1

And the answer for this test is "2\n0 2", as in the sample

Is this test correct?


Edited by author 15.02.2007 00:05

Problem statement was updated:
• "N >= 2" instead of "N >= 1"
• "Crossroads are numbered from 0 to N – 1, categories are numbered from 0 to K – 1"

New tests have been added.
Timelimit was decreased to 3 seconds.
Submissions made after contest have been rejudged.