QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#503591 | #8806. Summer Driving | EXODUS | 1 | 3147ms | 129340kb | C++17 | 4.8kb | 2024-08-03 20:28:05 | 2024-08-03 20:28:06 |
Judging History
answer
// test
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = - f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x *= f;
}
const int N = 3e5 + 10, inf = 1e9;
int n, R, a, b, dfn[N], nfd[N], rdfn[N], dfscnt, dep[N], mn[N], mmn[N], l[N], r[N];
vector <int> v[N], t[N];
priority_queue <int, vector <int>, greater <int>> q[N];
void predfs(int x, int fa) {
mn[x] = x;
nfd[dfn[x] = ++dfscnt] = x;
t[dep[x] = dep[fa] + 1].push_back(dfn[x]);
q[x].push(x);
int mn1 = x, id = x, mn2 = inf;
for (int i: v[x])
if (i != fa) {
predfs(i, x);
while (dep[q[i].top()] - dep[x] > b) q[i].pop();
chkmin(mn[x], q[i].top());
if (q[i].top() < mn1) {
mn2 = mn1;
mn1 = q[i].top();
id = i;
} else chkmin(mn2, q[i].top());
if (q[i].size() > q[x].size()) swap(q[i], q[x]);
while (q[i].size()) {
q[x].push(q[i].top());
q[i].pop();
}
}
for (int i: v[x])
if (i != fa) mmn[i] = id == i ? mn2 : mn1;
rdfn[x] = dfscnt;
if (dep[x] + a - 1 <= n) l[x] = lower_bound(all(t[dep[x] + a - 1]), dfn[x]) - t[dep[x] + a - 1].begin(), r[x] = upper_bound(all(t[dep[x] + a - 1]), rdfn[x]) - t[dep[x] + a - 1].begin();
}
int k, p[N];
int tag[N << 2];
template<typename info_t,typename tag_t>struct Sgt{
#define ls(k) ((k)<<1)
#define rs(k) ((k)<<1|1)
struct node{info_t info;tag_t tag;}t[N<<2];
void apply(int k,tag_t v){t[k].info=t[k].info+v;t[k].tag=t[k].tag+v;}
void push(int k){if(t[k].tag!=tag_t())apply(ls(k),t[k].tag),apply(rs(k),t[k].tag),t[k].tag=tag_t();}
void pull(int k){t[k].info=t[ls(k)].info+t[rs(k)].info;}
void clear(){
for(int i=1;i<=4*n;i++)
t[i].info=info_t(),t[i].tag=tag_t();
}
void modify(int l,int r,int k,int ql,int qr,tag_t v){
if(ql>qr)return;
if(ql<=l&&r<=qr)return apply(k,v);
int mid=(l+r)>>1;push(k);
if(ql<=mid)modify(l,mid,ls(k),ql,qr,v);
if(mid<qr)modify(mid+1,r,rs(k),ql,qr,v);
pull(k);
}
info_t query(int l,int r,int k,int ql,int qr){
if(ql>qr)return info_t();
if(ql<=l&&r<=qr)return t[k].info;
int mid=(l+r)>>1;push(k);
info_t res=info_t();
if(ql<=mid){
if(mid<qr)res=query(l,mid,ls(k),ql,qr)+query(mid+1,r,rs(k),ql,qr);
else res=query(l,mid,ls(k),ql,qr);
}else res=query(mid+1,r,rs(k),ql,qr);
return res;
}
#undef ls
#undef rs
};
struct info_t{int val;info_t(int _val=0):val(_val){}};
struct tag_t{int tag;tag_t(int _tag=0):tag(_tag){}};
info_t operator +(info_t lhs,info_t rhs){return info_t(max(lhs.val,rhs.val));}
info_t operator +(info_t lhs,tag_t rhs){return info_t(max(lhs.val,rhs.tag));}
tag_t operator +(tag_t lhs,tag_t rhs){return tag_t(max(lhs.tag,rhs.tag));}
bool operator !=(tag_t lhs,tag_t rhs){return lhs.tag!=rhs.tag;}
Sgt<info_t,tag_t>sgt;
void dfs(int x, int fa) {
p[x] = inf;
int mn1 = inf, id, mn2 = inf;
for (int i: v[x])
if (i != fa) {
dfs(i, x), chkmin(p[x], p[i] + 1);
if (p[i] < mn1) {
mn2 = mn1;
mn1 = p[i];
id = i;
} else chkmin(mn2, p[i]);
}
int id1 = 0, id2 = 0;
int iid1 = 0, iid2 = 0;
for (int i: v[x])
if (i != fa) {
if (l[i] < r[i]) {
iid2 = iid1;
iid1 = i;
F(j, l[i], r[i] - 1) {
int e = nfd[t[dep[x] + a][j]];
if (p[e] > b && dep[e] > sgt.query(1, n, 1, dfn[e], dfn[e]).val) {
id2 = id1, id1 = i;
break;
}
}
}
sgt.modify(1, n, 1, dfn[i], rdfn[i], dep[x] + b - (id == i ? mn2 : mn1) - 1);
}
for (int i: v[x])
if (i != fa) {
bool flag;
if (!(iid1 == i ? iid2 : iid1)) flag = mmn[i] <= k;
else flag = !(id1 == i ? id2 : id1);
if (flag) sgt.modify(1, n, 1, dfn[i], rdfn[i], dep[x] + b);
}
bool flag;
if (!iid1) flag = mn[x] <= k;
else flag = !id1;
if (flag) p[x] = 0;
}
bool check() {
sgt.clear();
dfs(R, 0);
return p[R] == 0;
}
signed main() {
read(n), read(R), read(a), read(b);
if (a <= b) {
cout << 1;
return 0;
}
F(i, 1, n - 1) {
int x, y; read(x), read(y);
v[x].push_back(y);
v[y].push_back(x);
}
predfs(R, 0);
for(int i=1;i<=n;i++){
cout<<dfn[i]<<' '<<rdfn[i]<<' '<<mn[i]<<' '<<mmn[i]<<' '<<l[i]<<' '<<r[i]<<'\n';
}
int l = 0, r = n;
while (l + 1 < r) {
k = (l + r) >> 1;
if (check()) r = k;
else l = k;
}
cout << r;
if(r!=1)assert(false);
return 0;
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 10ms
memory: 39000kb
input:
300000 110732 1 1 54285 169439 18968 45543 130988 134682 162292 70081 212010 121474 128140 292466 209394 38279 91706 225569 67647 188578 265505 84279 161782 137098 27472 221980 284973 79104 230628 268631 69945 205947 153720 168119 230161 32244 138981 44376 165008 136947 125742 123375 209131 122038 8...
output:
1
result:
ok single line: '1'
Test #2:
score: 1
Accepted
time: 3ms
memory: 39068kb
input:
300000 123141 300000 300000 35459 173656 6934 241069 183095 87288 269195 16957 19492 242321 24470 81747 25697 172188 171424 220229 160473 69937 172168 99268 220664 39397 8212 2407 46718 94855 279515 295195 205222 167038 185958 111515 172553 45818 141322 214355 61335 64490 183502 105408 234540 245525...
output:
1
result:
ok single line: '1'
Test #3:
score: 1
Accepted
time: 6ms
memory: 38768kb
input:
298765 30225 2 3 265195 252069 113697 255482 227617 218688 279488 136408 179394 139291 86777 211320 255097 13136 68860 173342 178971 175020 278041 278319 285893 289677 194438 44163 56223 283058 110392 123602 20729 89517 152134 176747 121481 243463 297305 139297 244189 117068 181785 39468 154302 1860...
output:
1
result:
ok single line: '1'
Test #4:
score: 1
Accepted
time: 5ms
memory: 39128kb
input:
299987 224030 2 2 177674 20066 211112 287348 150440 136779 131528 209570 208840 36580 3395 152219 89118 44403 120439 274280 267578 80200 17796 257578 229408 211795 122773 147368 139779 842 94469 299092 211457 29057 9040 117449 216268 88141 40844 98163 183412 221031 230933 237086 147633 135982 282224...
output:
1
result:
ok single line: '1'
Test #5:
score: 1
Accepted
time: 6ms
memory: 39800kb
input:
2 1 1 2 2 1
output:
1
result:
ok single line: '1'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 3147ms
memory: 129340kb
input:
300000 226344 300 9 32176 183340 249597 14851 145160 92372 30564 242505 1140 169463 279867 14442 266653 32911 168819 26009 138049 133460 5327 103921 262703 112512 204338 84304 98144 9089 98632 238236 79093 101104 50327 237759 61236 275195 241153 116369 86842 272794 25675 121176 110170 225753 199931 ...
output:
134802 300000 1 46028 0 1 141510 300000 2 261846 0 1 220808 300000 3 98451 0 1 287175 300000 4 25167 0 1 55816 300000 5 136682 0 1 281707 300000 6 61271 0 1 114894 300000 7 151320 0 1 45111 300000 8 33178 0 1 157790 300000 9 37762 0 1 107647 300000 10 219899 0 1 110731 300000 11 84590 0 1 293636 300...
result:
wrong answer 1st lines differ - expected: '1', found: '134802 300000 1 46028 0 1'
Subtask #3:
score: 0
Runtime Error
Test #18:
score: 0
Runtime Error
input:
300 42 3 2 114 268 132 105 187 17 191 127 14 62 162 126 39 143 72 159 199 184 295 138 71 277 293 103 288 54 231 196 57 220 110 117 38 136 295 258 41 76 291 8 59 131 161 278 244 233 81 76 12 236 21 240 228 262 255 159 236 60 277 33 29 123 170 290 89 154 220 139 193 81 31 53 163 77 148 274 181 76 15 2...
output:
222 222 1 159 0 0 2 53 2 21 0 11 84 92 3 46 11 14 112 112 4 3 32 32 29 32 5 11 1 2 86 90 6 3 3 5 240 240 7 41 42 42 214 215 8 146 0 0 228 229 9 25 9 9 248 248 10 36 45 45 33 33 11 5 2 2 35 38 12 60 9 10 178 178 13 260 4 4 83 83 14 62 2 2 206 206 15 52 1 1 47 47 16 24 2 2 212 212 17 8 0 0 149 149 18 ...
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Runtime Error
Test #49:
score: 0
Runtime Error
input:
100000 20749 3 2 89778 51257 2293 75317 20142 42260 55350 69024 2419 90402 2248 71914 60607 94307 33933 57799 79884 93934 9788 53542 18109 28742 7700 93763 12102 78825 34580 61577 84344 12887 63610 12371 30988 75638 47533 66209 95296 22495 12638 545 36347 57495 41813 49592 60342 1881 38899 62345 524...
output:
71700 71705 1 54295 1626 1628 22434 22452 2 14622 2641 2646 77281 77281 3 34704 628 628 94362 94365 4 21551 9148 9149 30528 30548 5 14167 3477 3485 80815 80815 6 14246 274 274 80275 80275 7 60517 134 134 57752 57756 8 59618 2110 2111 59143 59143 9 20887 1416 1416 96010 96041 10 722 814 826 95441 954...
result:
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%