QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253917 | #4433. Kitten and Roomba | oogerbooger | ML | 0ms | 0kb | C++14 | 3.0kb | 2023-11-17 19:55:09 | 2023-11-17 19:55:10 |
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...