Submission #635429

#	Time	Username	Problem	Language	Result	Execution time	Memory
635429		NothingXD	Subtree (INOI20_subtree)	C++17	100 / 100	98 ms	25012 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, m, dp[maxn][4], h[maxn], par[maxn];
vector<int> g[maxn], ver[maxn];
bool vis[maxn];

int getpar(int v){
	return (par[v] < 0? v: par[v] = getpar(par[v]));
}

void merge(int u, int v){
	if ((u = getpar(u)) == (v = getpar(v))) return;
	if (par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
}

int dfs(int v, int p = -1){
	vis[v] = true;
	int mn = h[v];
	for (auto u: g[v]){
		if (!vis[u]){
			h[u] = h[v] + 1;
			mn = min(mn, dfs(u, v));
		}
		if (u != p){
			mn = min(mn, h[u]);
		}
	}
	if (mn < h[v]){
		merge(v, p);
	}
	return mn;
}

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int mul(int x, int y){
	return 1ll * x * y % mod;
}

bool cmp(int x, int y){
	return h[x] < h[y];
}

// dp[v][0] = ans
// dp[v][1] = bedone dost
// dp[v][2] = fagat dost khodet nisti
// dp[v][3] = dost hast khodet hasti bagie ham mitunan bashan

void solve(int v, int p = -1){
	vis[v] = true;
	dp[v][0] = dp[v][1] = dp[v][3] = 1;
	bool flg = false;
	for (auto u: g[v]){
		if (!vis[u]){
			solve(u, v);
			if (getpar(u) == getpar(v)){
				dp[v][0] = mul(dp[v][0], dp[u][0] + 1);
				dp[v][3] = mul(dp[v][3], dp[u][3]);
				dp[v][2] = add(dp[u][2], dp[u][3]);
			}
			else{
				dp[v][0] = mul(dp[v][0], dp[u][0] + 1);
				dp[v][1] = mul(dp[v][1], dp[u][0] + 1);
				dp[v][3] = mul(dp[v][3], dp[u][0] + 1);
			}
		}
		else if (u != p && h[u] > h[v]){
			flg = true;
		}
	}
	if (flg){
		int tmp = getpar(v);
		sort(all(ver[tmp]), cmp);
		int k = dp[v][1];
		for (int i = 1; i < ver[tmp].size(); i++){
			dp[v][0] = add(dp[v][0], mul(k, dp[ver[tmp][i]][2]));
			k = mul(k, dp[ver[tmp][i]][1]);
		}
		dp[v][0] = add(dp[v][0], -k);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	memset(par, -1, sizeof par);

	cin >> n >> m;

	for (int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);
	for (int i = 1; i <= n; i++){
		int tmp = getpar(i);
		ver[tmp].push_back(i);
	}
	memset(vis, false, sizeof vis);
	solve(1);

	int ans = 0;
	for (int i = 1; i <= n; i++) ans = add(ans, dp[i][0]);

	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(int, int)':
Main.cpp:106:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for (int i = 1; i < ver[tmp].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~

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