Submission #1003155

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

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 1e6 + 5;
const int LOG = 20;
const int mod = 1e9 + 7;

vector<int> adj[MXN];
vector<array<int, 2>> g[MXN];
int p[MXN], used[MXN], down[MXN], bak[MXN];
int in[MXN], t[MXN], tim;
int dp[MXN];

void _init(int a)
{
  t[a] = ++tim;
  used[a] = 1;
  for (array<int, 2> &v : g[a])
  {
    if (v[0] != p[a] && used[v[0]]) bak[v[1]] = 1;
  }
  for (array<int, 2> &v : g[a])
  {
    if (!used[v[0]]) 
    {
      p[v[0]] = a;
      _init(v[0]);
    }
  }
}

void dfs(int a)
{
  for (int &v : adj[a])
  {
    dfs(v);
  }
  if (down[a])
  {
    vector<int> path;
    int x = down[a];
    while (x)
    {
      path.push_back(x);
      in[x] = 1;
      if (x == a) break;
      else assert(!down[x]);
      x = p[x];
    }
    reverse(path.begin(), path.end());
    vector<int> sum(path.size(), 0);
    int co = 1;
    for (int i = (int)path.size() - 1; i >= 0; i--)
    {
      if (i == (int)path.size() - 1) co = (co * dp[path[i]]) % mod;
      else
      {
        for (int &v : adj[path[i]]) 
        {
          if (!in[v] && v != p[path[i]]) 
          {
            co = (co * (dp[v] + 1)) % mod;
          }
        }
      }
      sum[i] = ((i + 1 < path.size() ? sum[i + 1] : 0) + co) % mod;
    }
    co = 1;
    for (int i = 0; i + 1 < path.size(); i++)
    {
      for (int &v : adj[path[i]])
      {
        if (!in[v] && v != p[path[i]]) 
        {
          co = (co * (dp[v] + 1)) % mod;
        }
      }
      dp[a] = (dp[a] + co) % mod;
      if (i + 2 < path.size()) dp[a] = (dp[a] + ((sum[i + 2] * co) % mod)) % mod;
    }
    for (int x : path) in[x] = 0;
  }
  else
  {
    dp[a] = 1;
    for (int &v : adj[a])
    {
      dp[a] = (dp[a] * (dp[v] + 1)) % mod;
    }
  }
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++)
  {
    int u, v;
    cin >> u >> v;
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  _init(1);
  for (int a = 1; a <= n; a++)
  {
    for (array<int, 2> &v : g[a])
    {
      if (t[v[0]] > t[a] && !bak[v[1]]) adj[a].push_back(v[0]);
      else if (t[v[0]] > t[a] && bak[v[1]]) down[a] = v[0];
    }
  }
  dfs(1);
  int res = 0;
  for (int i = 1; i <= n; i++)
  {
    res = (res + dp[i]) % mod;
  }
  cout << res << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:70:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |       sum[i] = ((i + 1 < path.size() ? sum[i + 1] : 0) + co) % mod;
      |                  ~~~~~~^~~~~~~~~~~~~
Main.cpp:73:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i + 1 < path.size(); i++)
      |                     ~~~~~~^~~~~~~~~~~~~
Main.cpp:83:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |       if (i + 2 < path.size()) dp[a] = (dp[a] + ((sum[i + 2] * co) % mod)) % mod;
      |           ~~~~~~^~~~~~~~~~~~~

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