QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#253917#4433. Kitten and RoombaoogerboogerML 0ms0kbC++143.0kb2023-11-17 19:55:092023-11-17 19:55:10

Judging History

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

  • [2023-11-17 19:55:10]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-11-17 19:55:09]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define INF 1000000000
#define INFl 1000000000000000000
#define all(x) x.begin(), x.end()
#define sajz(x) (int)x.size()
#define pb push_back
#define se second
#define fi first
#define yes puts("YES")
#define no puts("NO")
#define erase_duplicates(x) {sort(all(x));(x).resize(distance((x).begin(), unique(all(x))));}
using namespace std;
//using namespace __gnu_pbds;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;
typedef multiset<int> msi;
typedef long double ld;
//typedef cc_hash_table<int, int, hash<int>> ht;

const int N = 1e6 + 5;

long double lazy[N], p[N];
int cnt[N], parent[N];
vi adj[N];

void dfs(int v, int par) {
	parent[v] = par;
	for (auto u : adj[v]) {
		if (u != par) dfs(u, v);
	}
}

void test_case() {
	int n, c;
	cin >> n >> c;

	c --;
	for (int i = 0; i < n; i ++) {
		cnt[i] = 0;
		lazy[i] = 0;
		p[i] = 0;
	}

	p[c] = 1;

	for (int i = 0; i < n - 1; i ++) {
		int a, b;
		cin >> a >> b;
		a --, b --;
		
		cnt[a] ++;
		cnt[b] ++;
		adj[a].pb(b);
		adj[b].pb(a);
	}

	dfs(0, -1);

	int k;
	cin >> k;
	vi a(k);
	long double ans = 0;
	for (int i = 0; i < k; i ++) {
		cin >> a[i];
		a[i] --;

		//debug(i, a[i]);

		if (parent[a[i]] != -1) p[a[i]] += lazy[parent[a[i]]];
		
		if (p[a[i]] > 1) p[a[i]] = 1;
		lazy[a[i]] += p[a[i]] / cnt[a[i]];
		if (lazy[a[i]] > 1) lazy[a[i]] = 1;
		p[parent[a[i]]] += p[a[i]] / cnt[a[i]];

		ans += p[a[i]];
		p[a[i]] = 0;
	}

	cout << fixed << setprecision(7) << ans << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	int t=1;
	cin >> t;
	for (int i = 1; i <= t; i ++) {
		test_case();
	}
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

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:


result: