Submission #1003103

#TimeUsernameProblemLanguageResultExecution timeMemory
1003103vjudge1Subtree (INOI20_subtree)C++17
12 / 100
38 ms24668 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 1e5 + 5; const int LOG = 20; const int mod = 1e9 + 7; vector<int> adj[MXN]; int p[MXN], used[MXN], down[MXN]; int in[MXN], t[MXN], tim; int dp[MXN]; void dfs(int a) { t[a] = ++tim; dp[a] = 0; used[a] = 1; for (int &v : adj[a]) { if (!used[v]) { p[v] = a; dfs(v); } else if (v != p[a] && t[v] < t[a]) { assert(!down[v]); down[v] = a; } } 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; adj[u].push_back(v); adj[v].push_back(u); } 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:60: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]
   60 |       sum[i] = ((i + 1 < path.size() ? sum[i + 1] : 0) + co) % mod;
      |                  ~~~~~~^~~~~~~~~~~~~
Main.cpp:63: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]
   63 |     for (int i = 0; i + 1 < path.size(); i++)
      |                     ~~~~~~^~~~~~~~~~~~~
Main.cpp:73: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]
   73 |       if (i + 2 < path.size()) dp[a] = (dp[a] + ((sum[i + 2] * co) % mod)) % mod;
      |           ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...