Sort by

recency

|

64 Discussions

|

  • + 0 comments
    vector<long> edges[100001];
    long d=1000000007;
    pair<long,long> dfs(int index,int p)
    {
        long lonely=1,total=1;
        for(int i=0;i<edges[index].size();i++)
        {
            if(edges[index][i]==p) continue;
            pair<long,long> current=dfs(edges[index][i],index);
            lonely=(lonely*current.first)%d;
            total=(total*(current.first+current.second))%d;
        }
        return {(total-lonely+d)%d,total};
    }
    int kingdomDivision(int n, vector<vector<int>> roads) 
    {
        for(auto& road: roads)
            edges[road[0]].push_back(road[1]), edges[road[1]].push_back(road[0]);
        pair<long,long> result=dfs(1,-1);
        return (2*result.first)%d;
    }
    
  • + 0 comments

    the test case 1 gives me a simple data Input (stdin):

    7; 1 2; 1 5; 2 3; 2 4; 5 6; 7 5;

    How is that possible to divide it six ways? I count only 4 because it is a particular case of the case in example, is not it?

  • + 0 comments

    Recursive solution doesn't work on Python because of the maximum recursion limit (e.g. Test 11 has a tree with 72000 depth). sys.setrecursionlimit(100000) doesn't work because Python still crashes at ~2670 level of recursion. What works: using Kahn's algorithm to iteratively go from the leaves to the root. New style Prescription wooden glasses

  • + 0 comments

    took me AGES to debug

    O(n)

    long mod = 1000000007;
    
    class Node {
    public:
        int number;
        long divide;
        long loneRed;
        Node* parent;
        vector<Node*> children;
        Node (int num, long div, long free, Node* par) {
            number = num; divide = div; loneRed = free; parent = par;
        }
    };
    
    Node* treeMaker (int n, const vector<vector<int>>& roads) {
        Node* root = new Node(1, 0, 1, NULL);
        vector<vector<int>> adj(n+1);
        for (int i=0; i < roads.size(); i++) {
            adj[roads[i][0]].push_back(roads[i][1]);
            adj[roads[i][1]].push_back(roads[i][0]);
        }
        queue<Node*> Q;
        Q.push(root);
        while (!Q.empty()) {
            Node* t = Q.front();
            for (int i=0; i < adj[t->number].size(); i++) {
                if (t == root or adj[t->number][i] != t->parent->number) {
                    Node* child = new Node(adj[t->number][i], 0, 1, t);
                    t->children.push_back(child);
                    Q.push(child);
                }
            }
            Q.pop();
        }
        return root;
    }
    
    void dehaka (Node* current) {
        if (current->children.empty()) return;
        long a = 1, b = 1;
        for (Node* child : current->children) {
            dehaka(child);
            b = (b * child->divide) % mod;
            a = (a * (2 * child->divide + child->loneRed)) % mod;
        }
        current->loneRed = b;
        current->divide = (a - b + mod) % mod;
    }
    
    int main()
    {
        int n, k, l;
        vector<vector<int>> roads;
        cin >> n;
        for (int i=1; i <= n-1; i++) {
            cin >> k >> l;
            roads.push_back({k, l});
        }
        Node* root = treeMaker(n, roads);
        dehaka(root);
        cout << (2 * root->divide) % mod;
    }
    
  • + 1 comment

    Why this is medium difficulty?