qwq

Edited by author 23.07.2023 08:21

Bitsets instead of binary_search helped me

Here is test generator that helped me beat TLE!

-------------------
#include <stdio.h>

void test1()
{
    FILE* stream = freopen ("BusRoutes.big", "w", stdout);
    const int n = 1000;
    const int endp = 100000;
    int cur = endp;
    printf ("%d 100000\n", n);
    for (int i = 0; i < n; ++i) {
        int cnt = (cur == 100) ? 100 : 200;
        printf ("%d ", cnt);
        for (int j = 0; j < cnt; ++j) {
             printf ("%d ", cur--);
        }
        printf ("\n");
        cur += 100;
    }
    printf ("1 %d\n", endp);
    fclose (stream);
}

int main()
{
    test1();
    return 0;
}
-------------------

New anti-(N*N*M) test was added. TL was decreased to 1 second (this TL better corresponds to original 3 seconds in 2006). About 100 authors lost AC.

Can someone help me to debug this C++ code? It got crash at 19th test-case.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

vector<int> p[1005];
vector<int> idxs[10005];
int dist[10005];
int bef[10005];
queue<int> q;

void print(int n)
{
    if(n!=-1)
    {
        print(bef[n]);
        printf("%d ",n);
    }
}

int main()
{
    int n,m,c,d,awl,akh,tmp;
    bool sudah = false;
    scanf("%d%d",&m,&n);
    for(c=0;c<=n;c++)
    {
        dist[c] = 10000000;
        bef[c] = -1;
    }
    for(c=0;c<m;c++)
    {
        scanf("%d",&d);
        while(d--)
        {
            scanf("%d",&tmp);
            p[c].push_back(tmp);
            idxs[tmp].push_back(c);
        }
    }
    scanf("%d%d",&awl,&akh);
    dist[awl] = 0;
    q.push(awl);
    while(!q.empty())
    {
        tmp = q.front();
        q.pop();
        n = idxs[tmp].size();
        for(c=0;c<n;c++)
        {
            m = p[idxs[tmp][c]].size();
            for(d=0;d<m;d++) if(p[idxs[tmp][c]][d]!=tmp) if(dist[p[idxs[tmp][c]][d]] > dist[tmp]+1)
            {
                dist[p[idxs[tmp][c]][d]] = dist[tmp] + 1;
                bef[p[idxs[tmp][c]][d]] = tmp;
                if(p[idxs[tmp][c]][d]==akh) sudah = true;
                else q.push(p[idxs[tmp][c]][d]);
            }
            if(sudah) break;
        }
        if(sudah) break;
    }
    if(dist[akh]==10000000)
    {
        printf("-1\n");
        return 0;
    }
    printf("%d\n",dist[akh]);
    print(akh);
    printf("\n");
    return 0;
}

Thanks in advance.

http://acm.timus.ru/status.aspx?space=1&pos=1061981

I advise everyone to learn good memory usage despite large memory limits.

Edited by author 01.03.2006 14:37

1434 = Bus Routes = Автобусные маршруты = 1137 :-D

like
...
3 10 6 8
4 10 6 9 11
...
???
please help

How is possible to exceed memory limit on test 19, and I'm using static memory in Pascal... That memory should be exceeded on the first test if it's larger than 32MB ?

Can anybody tell me, how to store and present graph in this problem??? There are too much edges and vertexes.

Sample Tests:
1 1
1 1
1 1
My output:
0
1
(Or should it be
0
1 1
?)

Another Sample Test:
1 2
2 1 2
1 1
My output:
0
1

Edited by author 28.02.2006 13:27

In what order of junctions?

Edited by author 25.02.2006 15:39

7'th test is the first test where we cann't get from A to B. If I output '-1' I get WA. I think that you missprinted something in problem statement or 7'th test is wrong.