TLE in PATHTIC using only simple DFS traversal

1

Problem Link
I had pre-calculated the factors p1, p2 and was using dfs to allocate p1 and p2 alternatively.

code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long ll;
constexpr ull a1 = 1482918936932394962, a2 = 1554749829221870235;
vector<int> G[105];
vector<ull> value(105);


void dfs(int source = 1, int prev = -1, int i = 0)
{
    if (i == 0)
        value[source] = a1;
    else
        value[source] = a2;

    for (auto &x : G[source])
    {
        if (x != prev)
            dfs(x, source, i ^ 1);
    }
}

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    register int test, i, j;
    cin >> test;

    int n, x, y;

    while (test--)
    {
        cin >> n;

        for (i = 0; i < n; i++)
        {
            cin >> x >> y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs();


        for (i = 1; i <= n; i++)
        {
            cout << value[i] << ' ';
        }
        cout << "\n";
        for(i = 1; i <= n; i++)
            G[i].clear();

    }


    return 0;
}

I even tried dfs using visited array, that’s also giving TLE

2

Try initialising the first loop from 1.
(0…n-1) actually iterates the loop n times whereas you need to iterate it just n-1 time.
Hope this solves the problem.

1 Like
3

Thank You,
i just wasted 4 hrs on this.

1 Like