Submission #1003241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003241		vjudge1	Subtree (INOI20_subtree)	C++17	20 / 100	88 ms	30996 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
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];
const long long mod = 1e9+7;
long long ans=0;
void dfsCalc(int c) {
  vis[c]=1;
  for(int at:cycles[c]) {
    dp[at]=1;
    for(int to:g[at]) {
      if(!vis[getCycle[to]]) {
        dfsCalc(getCycle[to]);
        dp[at] = (dp[at]*(dp[to]+1))%mod;
      }
    }
  }
  if(cycles[c].size()==1){
    ans+=dp[cycles[c][0]];
    ans%=mod;
    return;
  }
  for(int i = 0;i<cycles[c].size();i++) {
    for(int j = 0;j<cycles[c].size();j++) {
      long long prod = dp[cycles[c][j]];
      int sz=1;
      for(int k = i;k!=j;k=(k+1)%cycles[c].size()){
        prod=(prod*dp[cycles[c][k]])%mod;
        sz++;
      }
      if(sz==cycles[c].size())continue;
      ans+=prod;
      for(int k = i;k!=j;k=(k+1)%cycles[c].size()) {
        tmpdp[cycles[c][k]]+=prod;
      }
      tmpdp[cycles[c][j]]+=prod;
    }
  }
  for(int i:cycles[c]) {
    dp[i]=tmpdp[i];
    ans%=mod;
  }
}
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);
  cout << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'void dfsCalc(int)':
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int i = 0;i<cycles[c].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~~
Main.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int j = 0;j<cycles[c].size();j++) {
      |                   ~^~~~~~~~~~~~~~~~~
Main.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |       if(sz==cycles[c].size())continue;
      |          ~~^~~~~~~~~~~~~~~~~~

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