oj.uz

Submission #469102

# Submission time Handle Problem Language Result Execution time Memory
469102 2021-08-30T17:55:29 Z sinamhdv Subtree (INOI20_subtree) C++11
12 / 100
 154 ms 28868 KB 
// 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[v];
		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);

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

	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7500 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7436 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Incorrect 5 ms 7500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 12 ms 8908 KB Output is correct
3 Correct 126 ms 21812 KB Output is correct
4 Correct 154 ms 21764 KB Output is correct
5 Correct 116 ms 21856 KB Output is correct
6 Correct 117 ms 21748 KB Output is correct
7 Correct 135 ms 27184 KB Output is correct
8 Correct 129 ms 25208 KB Output is correct
9 Correct 131 ms 25284 KB Output is correct
10 Correct 96 ms 22812 KB Output is correct
11 Correct 98 ms 22300 KB Output is correct
12 Correct 135 ms 21660 KB Output is correct
13 Correct 129 ms 21660 KB Output is correct
14 Correct 95 ms 24576 KB Output is correct
15 Correct 144 ms 28268 KB Output is correct
16 Correct 131 ms 28868 KB Output is correct
17 Correct 143 ms 21572 KB Output is correct
18 Correct 123 ms 21812 KB Output is correct
19 Correct 128 ms 21572 KB Output is correct
20 Correct 85 ms 22332 KB Output is correct
21 Correct 86 ms 22496 KB Output is correct
22 Correct 102 ms 22432 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7500 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7436 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Incorrect 5 ms 7500 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7500 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7436 KB Output is correct
7 Correct 5 ms 7500 KB Output is correct
8 Incorrect 5 ms 7500 KB Output isn't correct
9 Halted 0 ms 0 KB -