oj.uz

Submission #634704

# Submission time Handle Problem Language Result Execution time Memory
634704 2022-08-24T17:34:00 Z S2speed Subtree (INOI20_subtree) C++17
12 / 100
 135 ms 35524 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;
vector<pll> cdj[maxn];
ll c[maxn] , o , dp[maxn] , ps[maxn] , pz[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(vector<ll> &v , 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(v , l , m) + cal(v , 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;
		return;
	}
	ll ind = -1 , sz = sze(cc[t]);
	for(ll i = 0 ; i < sz ; i++){
		if(cc[t][i] == r){
			ind = i;
			break;
		}
	}
	vector<ll> v;
	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] + 1;
	pz[0] = v[0];
	for(ll i = 1 ; i < vs ; i++){
		pz[i] = pz[i - 1] * v[i] % md;
		ps[i] = ps[i - 1] + pz[i]; ps[i] -= (ps[i] >= md) * 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(v , 0 , vs);
	return;
}

/*
6 7
1 2 2 3 3 1
4 5 5 6 6 4
3 4
*/

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 10 ms 15956 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 12 ms 15892 KB Output is correct
4 Correct 10 ms 15944 KB Output is correct
5 Correct 9 ms 15956 KB Output is correct
6 Correct 9 ms 15884 KB Output is correct
7 Correct 8 ms 15956 KB Output is correct
8 Incorrect 11 ms 15956 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 8 ms 15956 KB Output is correct
2 Correct 13 ms 16852 KB Output is correct
3 Correct 91 ms 25652 KB Output is correct
4 Correct 83 ms 25544 KB Output is correct
5 Correct 66 ms 25584 KB Output is correct
6 Correct 104 ms 25548 KB Output is correct
7 Correct 134 ms 33384 KB Output is correct
8 Correct 108 ms 30588 KB Output is correct
9 Correct 96 ms 31056 KB Output is correct
10 Correct 63 ms 26148 KB Output is correct
11 Correct 65 ms 25144 KB Output is correct
12 Correct 81 ms 24612 KB Output is correct
13 Correct 91 ms 24572 KB Output is correct
14 Correct 62 ms 28608 KB Output is correct
15 Correct 101 ms 34452 KB Output is correct
16 Correct 135 ms 35524 KB Output is correct
17 Correct 71 ms 24612 KB Output is correct
18 Correct 83 ms 24712 KB Output is correct
19 Correct 105 ms 24712 KB Output is correct
20 Correct 62 ms 25288 KB Output is correct
21 Correct 71 ms 25484 KB Output is correct
22 Correct 91 ms 25464 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 12 ms 15892 KB Output is correct
4 Correct 10 ms 15944 KB Output is correct
5 Correct 9 ms 15956 KB Output is correct
6 Correct 9 ms 15884 KB Output is correct
7 Correct 8 ms 15956 KB Output is correct
8 Incorrect 11 ms 15956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 12 ms 15892 KB Output is correct
4 Correct 10 ms 15944 KB Output is correct
5 Correct 9 ms 15956 KB Output is correct
6 Correct 9 ms 15884 KB Output is correct
7 Correct 8 ms 15956 KB Output is correct
8 Incorrect 11 ms 15956 KB Output isn't correct
9 Halted 0 ms 0 KB -