Codeforces Round #855 Div. 3 — Problem G — Symmetree

Revision en1, by KushagrJaiswal, 2023-03-08 14:41:52

I've taken the idea to solve this problem from here — https://codeforces.net/blog/entry/113465?#comment-1009818.

But, my solution is getting a TLE on test 11.

Here's my code -

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::map;
using std::sort;
using std::pair;
using std::make_pair;

void calculate_values(const vector<vector<int>>&, vector<int>&,
                      map<vector<int>, int>&, int, int);
void find_ans(const vector<vector<int>>&, const vector<int>&, bool&, int, int,
              int);

int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        vector<vector<int>> graph(n);

        for (int i = 0; i < (n - 1); ++i)
        {
            int u, v;
            cin >> u >> v;

            --u;
            --v;

            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        vector<int> values(n);
        map<vector<int>, int> table_of_values;
        calculate_values(graph, values, table_of_values, 0, -1);

        bool ans = true;
        find_ans(graph, values, ans, 0, -1, table_of_values.size());

        cout << (ans ? "YES\n" : "NO\n");
    }

    return 0;
}

void calculate_values(const vector<vector<int>>& graph, vector<int>& values,
                      map<vector<int>, int>& table_of_values, int vertex,
                      int parent)
{
    for (int child : graph[vertex])
        if (child != parent)
            calculate_values(graph, values, table_of_values, child, vertex);

    vector<int> children_values;
    for (int child : graph[vertex])
        if (child != parent)
            children_values.push_back(values[child]);
    sort(children_values.begin(), children_values.end());

    auto it = table_of_values.find(children_values);

    if (it != table_of_values.end())
    {
        values[vertex] = it->second;
    }

    else
    {
        int value = table_of_values.size();
        table_of_values[children_values] = value;
        values[vertex] = value;
    }
}

void find_ans(const vector<vector<int>>& graph, const vector<int>& values,
              bool& ans, int vertex, int parent, int size)
{
    int number_of_odd_occurrences = 0;
    int new_vertex;

    {
        vector<pair<int, int>> parities(size, make_pair(0, 0));

        for (int child : graph[vertex])
        {
            if (child != parent)
            {
                parities[values[child]].first ^= 1;
                parities[values[child]].second = child;
            }
        }

        for (int i = 0; i < size; ++i)
        {
            if (parities[i].first == 1)
            {
                ++(number_of_odd_occurrences);
                new_vertex = (parities[i].second);
            }
        }

        if (number_of_odd_occurrences >= 2)
        {
            ans = false;
            return;
        }
    }

    if (number_of_odd_occurrences == 1)
    {
        find_ans(graph, values, ans, new_vertex, vertex, size);
    }
}

Can someone please tell me how to improve my code?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English KushagrJaiswal 2023-03-08 14:41:52 3299 Initial revision (published)