QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132894 | #4240. Tree Circles | paradoxica11y | WA | 188ms | 36264kb | C++14 | 4.2kb | 2023-08-01 02:48:33 | 2023-08-01 02:48:39 |
Judging History
answer
// template by paradox & gege & parasat
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define se second
#define fi first
#define s second
#define f first
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef long double ld;
typedef long long ll;
//typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1e6 + 3, 1e6 + 7), mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, MOD = 998244353;
const ll INF = 1e18;
const int N = 3e5;
const int M = N + 7;
const int K = 1;
vector<int> bamboo[M], edges[M];
int par[M], pos[M];
int get_par(int v) {
return v == par[v] ? v : par[v] = get_par(par[v]);
}
void merge(int v, int u, int val) {
v = get_par(v);
u = get_par(u);
if (sz(bamboo[v]) < sz(bamboo[u]))
swap(v, u);
for (int x : bamboo[u])
bamboo[v].pb(x);
edges[v].pb(val);
for (int x : edges[u])
edges[v].pb(x);
par[u] = v;
}
struct segment_tree {
static const int TN = N;
int g[TN << 2];
void upd(int v) {
g[v] = max(g[v << 1], g[v << 1 | 1]);
}
void build(const vector<int> &vals, int v = 1, int tl = 1, int tr = TN) {
if (tl == tr) {
g[v] = tl <= sz(vals) ? vals[tl - 1] : 0;
return;
}
int tm = (tl + tr) >> 1;
build(vals, v << 1, tl, tm);
build(vals, v << 1 | 1, tm + 1, tr);
upd(v);
}
int get(int l, int r, int v = 1, int tl = 1, int tr = TN) {
if (l > r || tl > r || l > tr)
return 0;
if (l <= tl && tr <= r)
return g[v];
int tm = (tl + tr) >> 1;
int le = get(l, r, v << 1, tl, tm);
int ri = get(l, r, v << 1 | 1, tm + 1, tr);
return max(le, ri);
}
} t;
void solve() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
par[i] = i;
bamboo[i].pb(i);
}
for (int i = 1; i < n; i++) {
int v, u;
scanf("%d %d", &v, &u);
merge(v, u, i);
}
int root = get_par(1);
vector<int> &ord = bamboo[root];
vector<int> &edg = edges[root];
assert(sz(ord) == sz(edg) + 1);
// cerr << "bamboo -> ";
// for (int v : ord)
// cerr << v << " ";
// cerr << " <-\n";
// cerr << "edges -> ";
// for (int x : edg)
// cerr << x << " ";
// cerr << " <-\n";
t.build(edg);
for (int i = 0; i < sz(ord); i++)
pos[ord[i]] = i;
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int k;
scanf("%d", &k);
vector<int> ver;
for (int j = 1; j <= k; j++) {
int v;
scanf("%d", &v);
ver.pb(v);
}
sort(all(ver), [&](const int &v, const int &u) {
return pos[v] < pos[u];
});
vector<int> vals;
for (int i = 1; i < sz(ver); i++) {
int l = pos[ver[i - 1]], r = pos[ver[i]];
int val = t.get(l + 1, r);
if (!vals.empty())
vals.back() = min(vals.back(), val);
else
vals.pb(val);
vals.pb(val);
}
// cerr << "r :: ";
// for (int x : vals)
// cerr << x << ' ';
// cerr << " *\n";
int ans = 1;
for (int x : vals)
ans = 1ll * ans * x % MOD;
printf("%d\n", ans);
}
}
int main() {
int TT;
TT = 1;
// scanf("%d", &TT);
for (int tt = 1; tt <= TT; ++tt) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 24816kb
input:
3 1 2 2 3 2 3 1 2 3 2 1 3
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: 0
Accepted
time: 60ms
memory: 24864kb
input:
1000 251 1 610 251 1 621 610 534 617 1 27 617 54 534 251 435 610 984 1 850 291 610 251 461 51 27 376 617 461 310 36 850 36 351 456 461 461 171 456 294 949 294 688 1 833 610 174 534 435 841 841 60 556 251 251 423 655 376 688 188 610 448 456 549 894 841 65 688 65 522 421 435 382 65 894 613 617 789 880...
output:
275623202 374067774 494473471 420011499 643061355 554361044 755532440 289845686 45368764 527834219 925520205 659238238 433870012 469990636 657873561 852213216 966862980 542663190 982471669 458857532 478701698 947460452 451178245 603042191 422792889 685952031 417241570 548357718 223143158 101179924 9...
result:
ok 1000 numbers
Test #3:
score: 0
Accepted
time: 5ms
memory: 24844kb
input:
2000 1 1229 1229 743 7 1229 7 1684 293 1 1652 293 1458 743 293 1912 1912 1726 359 1458 372 743 772 293 756 1 409 1726 1652 921 433 1912 359 1515 1458 1897 1458 1439 409 952 1439 1877 1298 756 743 1055 1665 1897 1313 743 743 978 1515 1099 627 409 1665 1318 921 1859 293 39 627 1954 1665 646 1055 1584 ...
output:
985661081 289663642 426379198 961782139 145012705 45028730 513933554 853668549 529541313 702845230
result:
ok 10 numbers
Test #4:
score: -100
Wrong Answer
time: 188ms
memory: 36264kb
input:
300000 1 265092 1 46487 265092 220364 124925 1 1 288590 265092 156898 280571 46487 184789 220364 280571 151321 280571 66880 86168 151321 151321 273555 46487 112431 124925 45049 1 66769 112431 36492 86168 137565 251083 66880 143467 66880 284087 1 280571 112916 112431 254872 238475 280571 180865 36492...
output:
425265333 650921663 28695301 191498362 567238295 582516091 948253770 242063171 597569966 190082202 1 521207503 1 570927982 122195019 889056495 982165169 1 70088500 224396729 443558073 770844475 992420728 129019298 66932621 140351691 402404024 748029355 324810833 847382658 975494158 238329979 4835401...
result:
wrong answer 11th numbers differ - expected: '300000', found: '1'