Submission #782874

#	Time	Username	Problem	Language	Result	Execution time	Memory
782874		Sami_Massah	Subtree (INOI20_subtree)	C++11	38 / 100	553 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;


const int maxn = 1e5 + 12, mod = 1e9 + 7;
long long n, m, pd[maxn], h[maxn], dp[maxn], sum[maxn];
vector <int> conn[maxn], nums;
bitset <maxn> marked, in_nums;
void dfs(int u, int p = -1){

    marked[u] = 1;
    int me = -1;
    for(int v: conn[u])
        if(!marked[v]){
            pd[v] = u;
            h[v] = h[u] + 1;
            dfs(v, u);
        }
        else if(h[u] < h[v])
            me = v;
   // cout << u << ' ' << me << endl;
    if(me == -1){
        dp[u] = 1;
        for(int v: conn[u])
            if(h[u] < h[v]){
            //    cout << u << '-' << v << endl;
                dp[u] = (dp[u] * (dp[v] + 1)) % mod;
    }
        dp[u] %= mod;
        //cout << u << "->" << dp[u] << endl;
    }
    else{
        nums.clear();
        in_nums = 0;
        while(h[u] <= h[me] && me){
            nums.push_back(me);
            in_nums[me] = 1;
            me = pd[me];
        }
        for(int j = 0; j <= nums.size(); j++)
            sum[j] = 0;
        long long res = 1;
        for(int j = 0; j < nums.size(); j++){

            int nu = nums[j];
            for(int v: conn[nu])
                if(h[nu] < h[v] && !in_nums[v]){
                    res = res * (dp[v] + 1) % mod;
                    res %= mod;
                }
            sum[j] = (j == 0? 1: sum[j - 1]);
            sum[j] += res;
            sum[j] %= mod;
          //  cout << nu << ' ' << sum[j] << endl;

        }
       // cout << dp[2] << endl;
        res = 1;
        for(int j = nums.size() - 1; j >= 1; j--){
            int nu = nums[j];
            for(int v: conn[nu])
                if(h[nu] < h[v] && !in_nums[v]){
                    res = res * (dp[v] + 1) % mod;
                }
            res %= mod;
            if(j - 2 >= 0)
                dp[u] += res % mod * (sum[j - 2] % mod) % mod;
            dp[u] %= mod;
        }
        //cout << dp[2] << endl;
        dp[u] += res;
        dp[u] %= mod;
    }


}
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
   // cout << endl;
    dfs(1);
    long long ans = 0;
   // cout << endl;
    for(int i = 1; i <= n; i++){
        ans += dp[i];
        ans %= mod;
       // cout << i << ' ' << dp[i] << endl;
        }
    cout << ans << endl;









}
/*    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1;
    }
    int ans = 0;
    cout << endl;
    for(int i = 0; i < (1 << n); i++){
        for(int j = 0; j < n; j++)
            if((i >> j) & 1)
                p.push_back(j + 1);
        int num = 0;
        for(int j = 0; j < p.size(); j++)
            for(int c = j; c < p.size(); c++)
                if(e[p[j]][p[c]])
                    num += 1;
        if(num == p.size() - 1){
            if(p[0] == 1){
                for(int j: p)
                    cout << j << ' ';
                cout << endl;
            }
            ans += 1;

        }
        p.clear();

    }
    cout << ans << endl;
*/

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 0; j <= nums.size(); j++)
      |                        ~~^~~~~~~~~~~~~~
Main.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j = 0; j < nums.size(); j++){
      |                        ~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 12
• Subtask 3: 30 / 30
• Subtask 4: 0 / 50