Submission #1003339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003339		vjudge1	Subtree (INOI20_subtree)	C++17	100 / 100	100 ms	36864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const long long mod = 1e9+7;
long long binpow(long long a, long long b, long long MOD=mod) {
  a%=MOD;
  long long res = 1;
  while(b) {
    if(b&1){ 
      res=(res*a)%MOD;
    }
    a=(a*a)%MOD;
    b>>=1ll;
  }
  res%=MOD;
  return res;
}
vector<int> g[N];
vector<int> bridges[N];
vector<int> notBridges[N];
int add[N], depth[N];
bool vis[N];
vector<vector<int>> cycles;
int getCycle[N];
void dfsAdd(int at, int p) {
  vis[at]=1;
  for(int to:g[at]) {
    if(to==p)continue;
    if(vis[to] == 1) 
    {
      if(depth[at] > depth[to]) {
        add[at]++;
        add[to]--;
        notBridges[to].push_back(at);
        notBridges[at].push_back(to);
      }
      continue;
    }
    depth[to]=depth[at]+1;
    dfsAdd(to, at);
  }
}
void dfsGetBridges(int at, int p) {
  vis[at]=1;
  for(int to:g[at]) {
    if(vis[to])continue;
    dfsGetBridges(to, at);
    add[at]+=add[to];
  }
  if(p==0)return;
  if(add[at] == 0) {
    bridges[at].push_back(p);
    bridges[p].push_back(at);
  }
  else {
    notBridges[at].push_back(p);
    notBridges[p].push_back(at);
  }
}
vector<int> tempcycle;
void dfsGetCycles(int at) {
  tempcycle.push_back(at);
  vis[at]=1;
  for(int to:notBridges[at]) {
    if(vis[to])continue;
    dfsGetCycles(to);
  }
}
long long dp[N], tmpdp[N];
long long ans=0;
void dfsCalc(int c, int cc) {
  vis[c]=1;
  for(int at:cycles[c]) {
    dp[at]=1;
    for(int to:g[at]) {
      if(!vis[getCycle[to]]) {
        dfsCalc(getCycle[to], to);
        dp[at] = (dp[at]*(dp[to]+1))%mod;
      }
    }
  }
  if(cycles[c].size()==1){
    ans+=dp[cycles[c][0]];
    ans%=mod;
    return;
  }
  if(cc == -1) {
    cc=cycles[c][0];
  }


  int idx=0;
  for(int i = 0;i<cycles[c].size();i++) {
    if(cycles[c][i] == cc ) {
      idx=i;
    }
  }
  vector<int> cycle;
  for(int i = idx+1;i<cycles[c].size();i++)cycle.push_back(cycles[c][i]);
  for(int i = 0;i<idx;i++)cycle.push_back(cycles[c][i]);
  long long prod = 1;
  long long divsum = 1;
  int ss = cycle.size();
  int pref[ss];
  for(int i = 0;i<cycle.size();i++) {
    prod*=dp[cycle[i]];
    prod%=mod;
    ans += (prod*divsum)%mod;
    divsum = (divsum + binpow(prod, mod-2))%mod;
    pref[i] = prod;
  }
  for(int i = 1;i<cycle.size();i++) {
    pref[i] = (pref[i-1]+pref[i])%mod;
  }
  divsum=0;
  prod = dp[cc];
  {
    int i = cycle.size();
    ans=(ans+prod)%mod;
    tmpdp[cc] = (tmpdp[cc]+prod)%mod;
    ans=(ans+(prod*(pref[i-2]))%mod)%mod;
    tmpdp[cc] = (tmpdp[cc]+prod*(pref[i-2]))%mod;
  }
  for(int i = cycle.size()-1;i>=0;i--){ 
    prod = (prod*dp[cycle[i]])%mod;
    if(i!=0) {
      ans=(ans+prod)%mod;
      tmpdp[cc] = (tmpdp[cc]+prod)%mod;
    }
    if(i >= 2) {
      ans=(ans+(prod*(pref[i-2]))%mod)%mod;
      tmpdp[cc] = (tmpdp[cc]+prod*(pref[i-2]))%mod;
    }
  }
  dp[cc] = tmpdp[cc];
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  for(int i = 0;i<m;i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfsAdd(1, 0);
  memset(vis, 0, sizeof vis);
  dfsGetBridges(1, 0);
  memset(vis, 0, sizeof vis);
  for(int i = 1;i<=n;i++) {
    if(vis[i] == 0) {
      dfsGetCycles(i);
      for(int c:tempcycle) {
        getCycle[c] = cycles.size();
      }
      cycles.push_back(tempcycle);
      tempcycle.clear();
    }
  }
  memset(vis, 0, sizeof vis);
  dfsCalc(0, -1);
  cout << ans%mod << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'void dfsCalc(int, int)':
Main.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i = 0;i<cycles[c].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~~
Main.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i = idx+1;i<cycles[c].size();i++)cycle.push_back(cycles[c][i]);
      |                     ~^~~~~~~~~~~~~~~~~
Main.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i = 0;i<cycle.size();i++) {
      |                 ~^~~~~~~~~~~~~
Main.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int i = 1;i<cycle.size();i++) {
      |                 ~^~~~~~~~~~~~~

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