Submission #469104

#	Time	Username	Problem	Language	Result	Execution time	Memory
469104		sinamhdv	Subtree (INOI20_subtree)	C++11	100 / 100	181 ms	27740 KiB

Main

// INOI20_subtree
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 100100;
const int MAXE = 150100;

int n, m;
vector<int> adj[MAXN];
int ef[MAXE], eto[MAXE];
int hei[MAXN];
bool iscut[MAXE];
bool mark[MAXN];
vector<int> comp[MAXN];
int cn, cnum[MAXN];
vector<int> tree[MAXN];
int head[MAXN], vpar[MAXN];
int dp[MAXN][2];
int wei[MAXN];

inline void addedge(int x, int y)
{
	tree[x].pb(y);
	tree[y].pb(x);
}

inline int dfs1(int v, int epar)
{
	mark[v] = true;
	int dp = hei[v];
	for (int e : adj[v]) if (e != epar)
	{
		int u = eto[e] ^ ef[e] ^ v;
		if (mark[u]) dp = min(dp, hei[u]);
		else hei[u] = hei[v] + 1, dp = min(dp, dfs1(u, e));
	}
	if (dp >= hei[v] && epar >= 0) iscut[epar] = true;
	return dp;
}

void dfs2(int v)
{
	cnum[v] = cn;
	comp[cn].pb(v);
	for (int e : adj[v]) if (!iscut[e])
	{
		int u = ef[e] ^ eto[e] ^ v;
		if (!cnum[u]) dfs2(u);
	}
}

void dfs3(int v)
{
	mark[v] = true;
	for (int e : adj[v])
	{
		int u = ef[e] ^ eto[e] ^ v;
		if (mark[u]) continue;
		if (iscut[e])
		{
			head[cnum[u]] = u;
			vpar[cnum[u]] = v;
		}
		dfs3(u);
	}
}

void dfs4(int v, int par)
{
	for (int u : tree[v]) if (u != par)
	{
		dfs4(u, v);
		wei[vpar[u]] = (wei[vpar[u]] * ((ll)dp[u][1] + 1)) % mod;
	}

	// calc dp
	if ((int)comp[v].size() == 1)	// single vertex
	{
		dp[v][0] = dp[v][1] = wei[comp[v][0]];
		return;
	}
	
	// cycle
	int k = (int)comp[v].size();
	vector<int> ps(k + 5);
	
	ps[0] = 0;
	int cur = 1;
	FOR(i, 1, k + 1)
	{
		cur = (ll)cur * wei[comp[v][i - 1]] % mod;
		ps[i] = (ps[i - 1] + cur) % mod;
	}

	dbgr(ps.begin(), ps.end());

	cur = 1;
	for (int i = k - 1; i >= 1; i--)
	{
		dp[v][1] = (dp[v][1] + (ll)ps[i] * cur) % mod;
		cur = (ll)cur * wei[comp[v][i]] % mod;
	}

	dp[v][0] = dp[v][1];
	cur = 0;
	FOR(i, 1, k)
	{
		cur = wei[comp[v][i]] * ((ll)cur + 1) % mod;
		dp[v][0] = (dp[v][0] + cur) % mod;
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> m;
	FOR(i, 0, m)
	{
		cin >> ef[i] >> eto[i];
		adj[ef[i]].pb(i);
		adj[eto[i]].pb(i);
	}

	dfs1(1, -1);
	
	dbgr(iscut, iscut + m);

	FOR(i, 1, n + 1) if (!cnum[i]) cn++, dfs2(i);

	memset(mark, 0, sizeof(mark));
	dfs3(1);
	head[cnum[1]] = 1;

	FOR(i, 0, m) if (iscut[i]) addedge(cnum[ef[i]], cnum[eto[i]]);

	FOR(i, 1, cn + 1)
	{
		rotate(comp[i].begin(), find(all(comp[i]), head[i]), comp[i].end());
	}

	dbg(cn);
	FOR(i, 1, cn + 1)
	{
		dbg(i);
		dbg(head[i]);
		dbg(vpar[i]);
		dbgr(comp[i].begin(), comp[i].end());
	}

	fill(wei + 1, wei + n + 1, 1);
	dfs4(cnum[1], -1);

#ifdef DEBUG
	dbgr(wei + 1, wei + n + 1);
	FOR(i, 1, cn + 1) cout << "(" << dp[i][0] << ", " << dp[i][1] << ") ";
	cout << endl;
#endif

	ll ans = 0;
	FOR(i, 1, cn + 1) ans = (ans + dp[i][0]) % mod;
	ans = (mod + ans % mod) % mod;
	cout << ans << endl;

	return 0;
}

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