oj.uz

Submission #634668

# Submission time Handle Problem Language Result Execution time Memory
634668 2022-08-24T16:42:14 Z S2speed Subtree (INOI20_subtree) C++17
12 / 100
 89 ms 34096 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;

ll n , m , ans;
bitset<maxn> mark;
vector<ll> adj[maxn] , cc[maxn] , st , del , v;
vector<pll> cdj[maxn];
ll c[maxn] , o , dp[maxn] , ps[maxn];

void cDFS(ll r , ll par){
	st.push_back(r);
	mark[r] = true;
	for(auto i : adj[r]){
		if(i == par) continue;
		if(mark[i]){
			if(c[r] != -1) continue;
			while(st.back() != i){
				c[st.back()] = o;
				cc[o].push_back(st.back());
				del.push_back(st.back());
				st.pop_back();
			}
			c[i] = o;
			cc[o].push_back(i);
			o++;
			while(!del.empty()){
				st.push_back(del.back());
				del.pop_back();
			}
			continue;
		}
		cDFS(i , r);
	}
	st.pop_back();
	return;
}

ll cal(ll l , ll r){
	if(l >= r) return 0;
	if(r - l == 1) return v[l];
	ll m = (r + l) >> 1;
	ll a = 1 , b = 1 , h = 1;
	for(ll i = m - 1 ; i >= l ; i--){
		h *= v[i]; h %= md;
		a += h;
	}
	h = 1;
	for(ll i = m + 1 ; i < r ; i++){
		h *= v[i]; h %= md;
		b += h;
	}
	a %= md; b %= md;
	ll res = cal(l , m) + cal(m + 1 , r) + a * b % md * v[m];
	return res % md;
}

void dDFS(ll r , ll t , ll par , bool f = false){
//	cout<<r<<' '<<t<<' '<<par<<' '<<f<<endl;
	if(r < n){
		ll h = 1;
		for(auto p : cdj[r]){
			ll i = p.first , u = p.second;
			if(i == par) continue;
			dDFS(i , u , r);
			h *= dp[i] + 1; h %= md;
		}
		dp[r] = h;
		ans += h;
		return;
	}
	swap(r , t);
	if(f){
		ll h = 1;
		for(auto i : adj[r]){
			ll u = (c[i] == -1 ? i : c[i]);
			if(u == t) continue;
			dDFS(u , i , t);
			h *= dp[u] + 1; h %= md;
		}
		dp[r] = h;
		ans += h;
		return;
	}
	ll ind = -1 , sz = sze(cc[t]);
	for(ll i = 0 ; i < sz ; i++){
		if(cc[t][i] == r){
			ind = i;
			break;
		}
	}
	v.clear();
	for(ll i = ind + 1 ; i < sz ; i++){
		dDFS(t , cc[t][i] , par , true);
		v.push_back(dp[cc[t][i]]);
	}
	for(ll i = 0 ; i < ind ; i++){
		dDFS(t , cc[t][i] , par , true);
		v.push_back(dp[cc[t][i]]);
	}
	ll vs = sz - 1;
	ps[0] = v[0];
	for(ll i = 1 ; i < vs ; i++){
		ps[i] = ps[i - 1] * v[i] % md;
	}
	ll cur = 1 , res = 0;
	for(ll i = vs - 1 ; i > 0 ; i--){
		ll h = cur * ps[i - 1] % md;
		res += h;
		cur *= v[i]; cur %= md;
	}
	res += cur;
	dp[t] = res % md;
	ans += dp[t];
	ans += cal(0 , vs);
	return;
}

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

	memset(c , -1 , sizeof(c));
	cin>>n>>m; o = n;
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	cDFS(0 , -1);
	for(ll i = 0 ; i < n ; i++){
		ll v = (c[i] == -1 ? i : c[i]);
		for(auto j : adj[i]){
			ll u = (c[j] == -1 ? j : c[j]);
			if(v == u) continue;
			cdj[v].push_back({u , j});
		}
	}
	dDFS((c[0] == -1 ? 0 : c[0]) , 0 , -1);
	ans %= md;
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Incorrect 10 ms 15980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 13 ms 16852 KB Output is correct
3 Correct 80 ms 25604 KB Output is correct
4 Correct 75 ms 25664 KB Output is correct
5 Correct 80 ms 25564 KB Output is correct
6 Correct 83 ms 25684 KB Output is correct
7 Correct 83 ms 32200 KB Output is correct
8 Correct 79 ms 29984 KB Output is correct
9 Correct 73 ms 30308 KB Output is correct
10 Correct 52 ms 26136 KB Output is correct
11 Correct 56 ms 25076 KB Output is correct
12 Correct 72 ms 24660 KB Output is correct
13 Correct 77 ms 24652 KB Output is correct
14 Correct 70 ms 28220 KB Output is correct
15 Correct 89 ms 33136 KB Output is correct
16 Correct 80 ms 34096 KB Output is correct
17 Correct 74 ms 24612 KB Output is correct
18 Correct 73 ms 24600 KB Output is correct
19 Correct 67 ms 24584 KB Output is correct
20 Correct 73 ms 25408 KB Output is correct
21 Correct 50 ms 25520 KB Output is correct
22 Correct 56 ms 25412 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Incorrect 10 ms 15980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Incorrect 10 ms 15980 KB Output isn't correct
4 Halted 0 ms 0 KB -