QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#524735#4433. Kitten and Roombasroid_03AC ✓7824ms492004kbC++2011.2kb2024-08-20 02:37:562024-08-20 02:37:57

Judging History

你现在查看的是最新测评结果

  • [2024-08-20 02:37:57]
  • 评测
  • 测评结果:AC
  • 用时:7824ms
  • 内存:492004kb
  • [2024-08-20 02:37:56]
  • 提交

answer


#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T>using ind_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>using ind_mset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpll;
typedef vector<vl> vll;
template<class T> using maxpq = priority_queue<T>;
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec1 = vector<T>;
template<class T> using vec2 = vector<vector<T>>;
template<class T> using vec3 = vector<vector<vector<T>>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i,b,a)  for(ll i =((b)-1);i>=(a);i--)
#define mem(a,x)   memset(a,x,sizeof(a))
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(),(v).rend()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fbo(a) find_by_order(a) //will give a-th largest element
#define ook(a) order_of_key(a) //will give no. of elements strictly lesser than a
#define sz(x) ((int)(x).size())
#define nzl(x) __builtin_clzll(x)
#define nzr(x) __builtin_ctzll(x)
#define setbits(x) __builtin_popcountll(x)
#define setbitsParity(x) __builtin_parityll(x) // 1 -> odd else 0 if even
#define umap unordered_map
#define uset unordered_set
#define nl "\n"
#define PI atan(1)*4
#define E 2.71828
#define yes {cout << "Yes" << endl; return;}
#define no {cout << "No" << endl; return;}
#define YES {cout << "Yes" << endl;}
#define NO {cout << "No" << endl;}
#define nyet {cout<<"-1"<<endl;return;}
#define mxe(v)  (*max_element(v.begin(),v.end()))
#define mne(v)  (*min_element(v.begin(),v.end()))
#define unq(v)  v.resize(distance(v.begin(), unique(v.begin(), v.end())));
#define ub upper_bound
#define lb lower_bound
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
#define outt(a) \
	  FOR(i,1,sz(a))            \
	  cout << a[i] << " "; \
	  cout << endl;
#define inn(a) \
	  FOR(i,1,sz(a))            \
	  cin>>a[i];
#define FAST_AF_BOI                \
	ios_base ::sync_with_stdio(0); \
	cin.tie(0);               \
	cout.tie(0);

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
	  x += 0x9e3779b97f4a7c15;//abk
	  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
	  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
	  return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
	  static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
	  return splitmix64(x + FIXED_RANDOM);
  }
};
typedef gp_hash_table<long long,long long,custom_hash> fast_map;
typedef unordered_map<long long,long long,custom_hash> safe_map;

// ================================== i/o module ==================================
template <class T> void _print(T x){cerr<<x;};
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void read(T &x){x=0;int f=0;char ch=getchar();while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();x=f? -x:x;return ;}
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
template <class T> inline vector<T>& operator--(vector<T>& v) { for(auto &x:v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { for(auto &x:v) ++x; return v; }
template <class T> inline vector<T>& operator^=(vector<T>& v,int y) { for(auto &x:v) x^=y; return v; }
inline string& operator^=(string& s,int y) { for(auto &x:s)x=((x-'0')^y)+'0' ; return s; }

void dgb_out () { cerr << endl; }
template < typename Head, typename... Tail >
void dgb_out ( Head H, Tail... T) { cerr <<' ' << H; dgb_out (T...); }
#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dgb_out(__VA_ARGS__) 
#else
#define dbg(...)
#endif

// ================================================================================

//`````````````````````````````````````````````IMP FUNCTIONS``````````````````````````````````````````````````````
ll ceil(ll a,ll b){return (a+b-1)/b;}
int log_2(ull i){return i?nzl(1)-nzl(i):-1;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll bin_expo(ll a, ll b, ll mod) {ll res = 1;a%=mod;if(a==0)return 0;while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll bin_mul(ll a, ll b, ll mod) {ll res = 0; while (b > 0) {if (b & 1)res = (res + a) % mod; a = (a + a) % mod; b = b >> 1;} return res;}
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return bin_expo(a, b - 2, b);}
ll ncr(ll n, ll r, ll m, ll *fact, ll *ifact) {if(n<r)return 0;ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r];if(n < r) return 0;if(n == r || r == 0) return 1;if(r<0) return 0; return (((val1 * val2) % m) * val3) % m;}
void google(int t) {cout << "Case #" << t << ": ";}
vl sieve(int n) {int*arr = new int[n + 1](); vl vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i*i <= n; i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
ll large_expo(ll a,ll b,ll c,ll m) {return bin_expo(a,bin_expo(b,c,phin(m)),m);} //(a^b^c)%M 
ll large_expo_prime(ll a,ll b,ll c,ll m) {return bin_expo(a,bin_expo(b,c,m-1),m);} //(a^b^c)%M when m is prime
template<class T>vector<T> prefixSum(vector<T> v, bool flag){vector<T> ans;T sum = 0;if (flag){for (auto &e : v){sum += e;ans.eb(sum);}}else{ans.pb(0);REP(i, v.size(), 0){sum += v[i];ans.eb(sum);}reverse(all(ans));}return ans;}
ll ffs(ll n){if(n==0)return -1;return log2(n & -n);}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 
//````````````````````````````````````````````````````````````````````````````````````````````````````````````

const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 2000 + 10;
const ll mod1 = (1e9 + 7);
const ll mod2 = (998244353);

/*
Self notes cause I need it :
1. dumbfk read the question properly ... I m fed up with this lack of presence of mind
2. dont assume that something is given in question ,like the input is sorted or stuff
   if some step needs the input to be sorted , either check question or sort , dont assume
3. in case you have less time to debug : 
	Common errors :
	  -> Wrote wrong variable names at places cause ur stupid	
	 -> For debugging u hard coded small values and submitted that solution right away
*/

#define int long long

void transcendent(int tc)
{
	int n, c; cin >> n >> c;
	vec2<int> adj(n + 1);
	FOR(_, 0, n - 1) {
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vec1<int> up(n + 1);
	auto dfs = [&] (auto && dfs, int u, int p) -> void {
		up[u] = p;
		for(auto &v : adj[u]) if(v != p) dfs(dfs, v, u);
	}; dfs(dfs, c, 0);
	int m; cin >> m;
	vec1<int> ord(m); cin >> ord;
	set<int> pos[n + 1];
	FOR(i, 0, m) pos[ord[i]].insert(i);
	vec1<ld> dp(m + 1), updp(n + 1); //prob to meet here 
	ld ans = 0;
	auto nxt = [&] (int v, int i) {
		auto it = pos[v].lb(i);
		return it == pos[v].end()? m: *it;
	};
	int x = nxt(c, 0);
	auto pull = [&] (int i) {
		int x = ord[i];
		dp[i] += updp[up[x]];
		dp[nxt(x, i + 1)] -= updp[up[x]];	
	};
	auto push = [&] (int i) {
		int x = ord[i];
		int cnt = sz(adj[x]);
		updp[x] += dp[i] / cnt;
		dp[nxt(up[x], i)] += dp[i] / cnt;
 	};
	dp[x] = 1;
	FOR(i, x, m) {
		pull(i);
		ans += dp[i];
		push(i);
	}
	cout << ans << nl;
}

static void read(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
}

int32_t main()
{
	//read();
	FAST_AF_BOI
	 auto begin = std::chrono::high_resolution_clock::now();
	cout << fixed << setprecision(12);
	//cerr << fixed << setprecision(0);
	//clock_t timer;
	//timer = clock();
	//PreComp();
	int test = 1;
	cin >> test;
	FOR(tc, 1, test + 1)
	{
			//cerr << endl << "----Test:" << tc << "----" <<endl;
			transcendent(tc);
	}
	auto end = std::chrono::high_resolution_clock::now();
	 auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
	 //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7824ms
memory: 492004kb

input:

2
1000000 315562
969409 917725
324847 719085
524235 603427
576843 433171
75335 238378
266746 487233
80422 95099
594363 96140
858172 261406
958326 466109
233845 350950
863969 345645
689972 81395
395383 27274
93913 208983
523722 380358
108074 172341
130041 692304
737158 383812
752080 33646
154356 6672...

output:

5.609417341487
5.610505139293

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 4806ms
memory: 354952kb

input:

3
3 3
2 1
2 3
4000000
2 1 2 1 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 1 2 1 2 1 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 1 2 3 2 3 2 1 2 3 2 3 2 3 2 3 2 3 2 1 2 3 2 1 2 3 2 1 2 1 2 ...

output:

2000496.597357362309
4999999.000000000000
666788.778081496199

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 955ms
memory: 9604kb

input:

5050
178 146
7 29
45 132
140 19
48 80
50 147
24 98
176 94
45 124
3 161
36 94
4 33
24 81
94 123
4 15
12 170
152 95
55 152
24 131
94 32
121 150
37 167
146 80
65 152
99 150
24 60
8 29
5 163
64 50
93 67
19 13
24 153
80 152
29 120
67 59
138 48
5 17
19 35
94 116
57 142
80 53
6 45
29 80
150 40
47 161
62 94...

output:

3.474522174310
2.125000000000
23.954963507658
0.000000000000
2.500000000000
3.935962624588
3.106841545496
5.588792516971
3.106619646407
1.791666666667
5.555530717632
0.000000000000
4.868330775897
3.499328721323
0.000000000000
3.106851919765
5.672871589793
5.683284772799
0.000000000000
3.074000492018...

result:

ok 5050 numbers

Test #4:

score: 0
Accepted
time: 5945ms
memory: 491508kb

input:

2
1000000 315562
679816 923554
749026 119526
400361 398944
729861 38631
237682 984276
240713 304346
923009 28429
705303 35145
281546 196216
128884 76719
542097 696978
832261 79936
617939 739512
639643 738806
304260 52873
63627 552308
627252 842013
683909 619035
326617 406438
159332 82575
823300 4115...

output:

4.452640912528
4.446637996859

result:

ok 2 numbers

Test #5:

score: 0
Accepted
time: 7688ms
memory: 491756kb

input:

2
1000000 315562
575035 646638
803204 719085
692015 374086
755314 193304
776395 55874
976706 805712
217914 823156
919201 953003
149774 16297
569437 50630
191605 6485
126613 286636
24494 152244
160536 434534
692015 362579
892731 521828
374895 872623
583943 946248
226984 256881
130161 826314
247361 45...

output:

5.837554136542
4.271576397399

result:

ok 2 numbers

Test #6:

score: 0
Accepted
time: 5089ms
memory: 488272kb

input:

2
1000000 941595
260117 135833
814046 740606
747365 965295
391550 71159
728551 704248
786875 854209
980320 968654
685130 721737
464879 19066
485673 803636
761076 467129
693561 787751
69739 373415
994214 367199
13100 494671
996272 547209
992937 103917
484331 476434
493297 779246
882922 78092
622726 3...

output:

8.814814814815
11.332096366378

result:

ok 2 numbers

Extra Test:

score: 0
Extra Test Passed