oj.uz

Submission #796921

# Submission time Handle Problem Language Result Execution time Memory
796921 2023-07-28T23:16:24 Z ashcomp Subtree (INOI20_subtree) C++14
12 / 100
 58 ms 31964 KB 
#include<bits/stdc++.h>

using namespace std;
 
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef double db;

const ll INF = 1e9;
const ll maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

ll n , m , h[maxn] , dp[maxn] , p[maxn] , par[maxn] , other[maxn];
bool tp[maxn] , mark[maxn];
vector<ll> g[maxn] , ar[maxn] , sum[maxn] , pre[maxn] , suf[maxn];

void dfs0(ll v)
{
        mark[v] = 1;
        for(auto u : g[v]){
                if(u==p[v])continue;
                if(mark[u]==1 && h[v]>h[u]){
                        par[v] = u;
                        tp[u] = true; 
                        continue;
                }
                if(mark[u]==1)continue;
                p[u] = v;
                h[u] = h[v] + 1;
                dfs0(u);
                if(par[v]==-1)par[v] = par[u];
                if(par[v]==v)par[v] = -1;
        }
}

void dfs1(ll v)
{
        mark[v] = 1;
        dp[v] = 1;
        other[v] = 1;
        for(auto u : g[v]){
                if(u==p[v] || mark[u]==1){
                        continue;
                }
                dfs1(u);
                if(par[u]!=par[v] && par[u]!=v){
                        other[v] = (other[v] *(dp[u]+1))%mod;
                }
                dp[v] = (dp[v] * (dp[u]+1))%mod;
        }
        if(par[v]!=-1){
                ar[par[v]].push_back(other[v]);
        }
        if(tp[v]==1){
                dp[v] = 0;
                ar[v].push_back(other[v]);
                /**/
                ll sz = ar[v].size();
                for(int i=1; i<=sz; i++){
                        suf[v].push_back(0);
                        pre[v].push_back(0);
                        sum[v].push_back(1);
                }
                suf[v][sz-1]=ar[v][sz-1];
                for(int i=sz-2; i>=0; i--){
                        suf[v][i] = (suf[v][i+1]*ar[v][i])%mod;
                }
                pre[v][0] = ar[v][0];
                for(int i=1; i<sz; i++){
                        pre[v][i] = (pre[v][i-1]*ar[v][i])%mod;
                }
                sum[v][0]=1;
                for(int i=1; i<sz; i++){
                        sum[v][i] = (sum[v][i-1]+pre[v][i-1])%mod;
                }
                /**/
                // for(int i=0; i<sz; i++){
                //         cout<<ar[v][i]<<" ";
                // }cout<<"\n";
                // for(int i=0; i<sz; i++){
                //         cout<<suf[v][i]<<" ";
                // }cout<<"\n";
                // for(int i=0; i<sz; i++){
                //         cout<<pre[v][i]<<" ";
                // }cout<<"\n";
                // for(int i=0; i<sz; i++){
                //         cout<<sum[v][i]<<" ";
                // }cout<<"\n";
                /**/
                for(int i=0; i<sz-1; i++){
                        //cout<<sum[v][i]*suf[v][i+1]<<" ";
                        dp[v] = (dp[v] + (sum[v][i]*suf[v][i+1])%mod)%mod;
                }//cout<<"\n";
        }
        //cout<<v<<" : "<<dp[v]<<" , "<<other[v]<<"\n";
}

int main()
{
        ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
        cin>>n>>m;
        for(int i=1; i<=m; i++){
                int v,u; cin>>v>>u;
                g[v].push_back(u);
                g[u].push_back(v);
        }
        for(int i=1; i<=n; i++){
                p[i] = -1;
                par[i] = -1;
        }
        dfs0(1);
        // for(int i=1; i<=n; i++){
        //         cout<<i<<" : "<<p[i]<<" , "<<par[i]<<"\n";
        // }
        for(int i=1; i<=n; i++){
                mark[i] = 0;
        }
        dfs1(1);
        ll ans = 0;
        for(int i=1; i<=n; i++){
                ans = (ans + dp[i])%mod;
        }
        // for(int i=1; i<=n; i++){
        //         cout<<i<<" : "<<dp[i]<<"\n";
        // }cout<<"\n";
        cout<<ans;
        return 0;
}
/*
5 5
1 2
2 3
3 4
4 1
4 5

ans = 19;
*/
/*
5 4
1 2
1 3
2 4
2 5

ans = 17;
*/
/*
8 9
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4
7 8

ans = 52;
*/
/*
by
          _____                    _____                    _____                    _____                  
         /\    \                  /\    \                  /\    \                  /\    \                 
        /::\    \                /::\    \                /::\____\                /::\    \                
       /::::\    \              /::::\    \              /:::/    /                \:::\    \               
      /::::::\    \            /::::::\    \            /:::/    /                  \:::\    \              
     /:::/\:::\    \          /:::/\:::\    \          /:::/    /                    \:::\    \             
    /:::/__\:::\    \        /:::/__\:::\    \        /:::/____/                      \:::\    \            
   /::::\   \:::\    \       \:::\   \:::\    \      /::::\    \                      /::::\    \           
  /::::::\   \:::\    \    ___\:::\   \:::\    \    /::::::\    \   _____    ____    /::::::\    \          
 /:::/\:::\   \:::\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \  /\   \  /:::/\:::\    \         
/:::/  \:::\   \:::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\/::\   \/:::/  \:::\____\        
\::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /\:::\  /:::/    \::/    /        
 \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    /  \:::\/:::/    / \/____/         
          \::::::/    /    \:::\   \:::\    \               \::::::/    /    \::::::/    /                  
           \::::/    /      \:::\   \:::\____\               \::::/    /      \::::/____/                   
           /:::/    /        \:::\  /:::/    /               /:::/    /        \:::\    \                   
          /:::/    /          \:::\/:::/    /               /:::/    /          \:::\    \                  
         /:::/    /            \::::::/    /               /:::/    /            \:::\    \                 
        /:::/    /              \::::/    /               /:::/    /              \:::\____\                
        \::/    /                \::/    /                \::/    /                \::/    /                
         \/____/                  \/____/                  \/____/                  \/____/                 
                                                                                                            
*/
//NOGHRE SHODANAM BAD NIST :_)

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12080 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12084 KB Output is correct
7 Correct 6 ms 12084 KB Output is correct
8 Incorrect 6 ms 11988 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12080 KB Output is correct
2 Correct 9 ms 12952 KB Output is correct
3 Correct 45 ms 20948 KB Output is correct
4 Correct 43 ms 20912 KB Output is correct
5 Correct 43 ms 20892 KB Output is correct
6 Correct 41 ms 20880 KB Output is correct
7 Correct 54 ms 29504 KB Output is correct
8 Correct 56 ms 26528 KB Output is correct
9 Correct 58 ms 26564 KB Output is correct
10 Correct 35 ms 21468 KB Output is correct
11 Correct 35 ms 20800 KB Output is correct
12 Correct 43 ms 20336 KB Output is correct
13 Correct 43 ms 20300 KB Output is correct
14 Correct 39 ms 24560 KB Output is correct
15 Correct 54 ms 30796 KB Output is correct
16 Correct 58 ms 31964 KB Output is correct
17 Correct 43 ms 20372 KB Output is correct
18 Correct 49 ms 20392 KB Output is correct
19 Correct 44 ms 20380 KB Output is correct
20 Correct 32 ms 21092 KB Output is correct
21 Correct 32 ms 21172 KB Output is correct
22 Correct 34 ms 21164 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12080 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12084 KB Output is correct
7 Correct 6 ms 12084 KB Output is correct
8 Incorrect 6 ms 11988 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12080 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12084 KB Output is correct
7 Correct 6 ms 12084 KB Output is correct
8 Incorrect 6 ms 11988 KB Output isn't correct
9 Halted 0 ms 0 KB -