QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#90815#5828. 游戏joke3579100 ✓713ms139788kbC++147.6kb2023-03-25 15:57:482023-03-25 15:57:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-25 15:57:52]
  • 评测
  • 测评结果:100
  • 用时:713ms
  • 内存:139788kb
  • [2023-03-25 15:57:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
namespace Fread  { const int SIZE = (1 << 18); char buf[SIZE], *p1 = buf, *p2 = buf; inline char getchar() {return (p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);} }
namespace Fwrite { const int SIZE = (1 << 18); char buf[SIZE], *S = buf, *T = buf+SIZE; inline void flush(){ fwrite(buf, 1, S-buf, stdout), S = buf; }  struct NTR{ ~NTR() { flush(); } }ztr;inline void putchar(char c){ *S++ = c; if(S == T) flush(); } }
#ifdef ONLINE_JUDGE
	#define getchar Fread::getchar
	#define putchar Fwrite::putchar
#endif
namespace Fastio{
	struct Reader{ template <typename T> Reader & operator >> (T & x) {char c = getchar(); bool f = false;while (c < '0' or c > '9') { if (c == '-') f = true;c = getchar();} x = 0;while(c >= '0' and c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} if (f) x = -x;return *this;}Reader&operator>>(char&c){ c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){ int len=0;char c=getchar(); while(c=='\n'||c==' '||c=='\r')c=getchar(); while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar(); str[len]='\0'; return *this;}Reader(){}}cin;
	struct Writer{ template <typename T> Writer & operator << (T   x) {if(x == 0) return putchar('0'), *this;if(x < 0) putchar('-'), x = -x;static int sta[45], top = 0; while (x)  sta[++top] = x %10, x /= 10; while (top)  putchar(sta[top] + '0'), --top; return *this;} Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer(){}}cout;
}   const char endl = '\n'; 
#define cin  Fastio :: cin
#define cout Fastio :: cout
#define inline __attribute__((__gnu_inline__, __always_inline__, __artificial__)) inline
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long; 
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, m, t1, t2, x, y, z, ans[N], dep[N], idfn[N], tmp[3], ttt[N][3];
pii mxv1[N][3], mxv2[N][3];
vi g[N];

struct elem { 
    int id, typ; 
    pii a[3]; 
} el[N];

struct sgt {
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define lzy(p) seg[p].lzy
    #define mxv(p) seg[p].mxv

    struct node {
        int lzy; pii mxv;
    } seg[N << 2];

    inline void ps_d(int p) {
        if (!lzy(p)) return;
        lzy(ls) += lzy(p), mxv(ls).first += lzy(p);
        lzy(rs) += lzy(p), mxv(rs).first += lzy(p);
        lzy(p) = 0;
    }

    void build(int p, int l, int r) {
        if (l == r) return void(mxv(p) = pii(dep[idfn[l]], idfn[l])); 
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        mxv(p) = max(mxv(ls), mxv(rs));
    }

    void update(int p, int l, int r, int L, int R, int va) {
        if (L > R) return;
        if (L <= l and r <= R) return lzy(p) += va, mxv(p).first += va, void();
        int mid = l + r >> 1; ps_d(p);
        if (L <= mid) update(ls, l, mid, L, R, va);
        if (mid < R) update(rs, mid + 1, r, L, R, va);
        mxv(p) = max(mxv(ls), mxv(rs));
    }

    pii query(int p, int l, int r, int L, int R) {
        if (L > R) return pii(0, 0);
        if (L <= l and r <= R) return mxv(p); 
        int mid = l + r >> 1; pii ret = { -1, -1 }; ps_d(p);
        if (L <= mid) ret = max(ret, query(ls, l, mid, L, R));
        if (mid < R) ret = max(ret, query(rs, mid + 1, r, L, R));
        return ret;
    }
} Tr;

struct fenwick {
    pii Index[N];
    inline pii query(int p, pii ret = pii(0, 0)) { 
        for (p++; p <= n; p += p & -p) ret = max(ret, Index[p]); 
        return ret; 
    }
    inline void update(int p, pii va) { 
        for (p++; p; p ^= p & -p) Index[p] = max(Index[p], va); 
    }
} fw;

int fa[N][21], siz[N], dfn[N], stp;
void dfs1(int u, int ft) {
    dfn[u] = ++ stp, idfn[stp] = u, siz[u] = 1;
    fa[u][0] = ft; rep(i, 1, 20) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto v : g[u]) if (v != ft) {
        dep[v] = dep[u] + 1, dfs1(v, u), siz[u] += siz[v];
    }
}

void dfs2(int u, int ft) {
    vp s; s.assign(3, { 0, u });
    for (auto v : g[u]) if (v != ft)
        s.eb(Tr.query(1, 1, n, dfn[v], dfn[v] + siz[v] - 1));
    s.eb(max(Tr.query(1, 1, n, 1, dfn[u] - 1), Tr.query(1, 1, n, dfn[u] + siz[u], n)));
    sort(s.begin(), s.end(), greater<>()); 
    rep(i, 0, 2) el[u].a[i] = mxv2[u][i] = s[i]; el[u].id = u;
    Tr.update(1, 1, n, 1, dfn[u] - 1, 1), Tr.update(1, 1, n, dfn[u] + siz[u], n, 1);
    for (auto v : g[u]) if (v != ft) {
        Tr.update(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, -1);
        dfs2(v, u);
        Tr.update(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, 1);
    } Tr.update(1, 1, n, 1, dfn[u] - 1, - 1), Tr.update(1, 1, n, dfn[u] + siz[u], n, - 1);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    pre(i, 20, 0) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    pre(i, 20, 0) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

int dis(int a, int b) { return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

int query(int u, int v, int dis) {
    int LCA = lca(u, v);
    if (dep[u] - dep[LCA] >= dis) {
        pre(i, 20, 0) if (fa[u][i] and dep[u] - dep[fa[u][i]] <= dis) dis -= dep[u] - dep[fa[u][i]], u = fa[u][i];
        return u;
    } else {
        dis -= dep[u] - dep[LCA];
        pre(i, 20, 0) if (fa[v][i] and dep[fa[v][i]] - dep[LCA] >= dis) v = fa[v][i];
        return v;
    }
}

signed main() {
    cin >> n;
    rep(i,2,n) cin >> t1 >> t2, g[t1].eb(t2), g[t2].eb(t1);
    dfs1(1, 0);
    Tr.build(1, 1, n);
    dfs2(1, 0);
    cin >> m;
    rep(i,1,m) {
        cin >> x >> y >> z; int s = (x + y + z) / 2; ttt[i][0] = x, ttt[i][1] = y, ttt[i][2] = z;
        mxv1[i][0] = pii(s - z, 0), mxv1[i][1] = pii(s - y, 1), mxv1[i][2] = pii(s - x, 2);
        sort(mxv1[i], mxv1[i] + 3, greater<>());
        rep(j, 0, 2) el[i + n].a[j] = mxv1[i][j];
        el[i + n].id = i, el[i + n].typ = 1;
    }
    sort(el + 1, el + n + m + 1, [&](auto a, auto b) {
        if (a.a[0].first == b.a[0].first) return a.typ < b.typ;
        return a.a[0].first > b.a[0].first;
    });
    rep(i,1,n + m) {
        if (el[i].typ == 0) fw.update(el[i].a[1].first, pii(el[i].a[2].first, el[i].id));
        else ans[el[i].id] = fw.query(el[i].a[1].first).second;
    }
    rep(i,1,m) {
        int x = ans[i];
        rep(j, 0, 2) tmp[mxv1[i][j].second] = query(x, mxv2[x][j].second, mxv1[i][j].first);
        if (*min_element(tmp, tmp + 3) == 0) {
            rep(u,1,n) rep(v,1,n) rep(w,1,n) if (dis(u, v) == ttt[i][0] and dis(u, w) == ttt[i][1] and dis(v, w) == ttt[i][2]) {
                cout << u << ' ' << v << ' ' << w << '\n';
                goto V;
            } V:;
        } else {
            rep(j, 0, 2) cout << tmp[j] << ' '; cout << '\n';
        }
    }
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 14ms
memory: 44136kb

input:

500
279 196
182 105
400 14
278 217
198 411
379 318
120 421
314 95
437 325
23 433
71 485
192 154
90 224
180 71
328 93
183 101
404 349
223 285
492 100
366 480
29 328
200 448
365 156
226 231
129 167
246 273
171 452
284 6
131 471
229 90
480 48
448 157
240 221
7 36
401 200
255 438
436 110
281 489
388 258...

output:

93 175 456 
421 47 239 
361 278 175 
238 136 473 
39 239 152 
132 110 361 
238 281 7 
203 125 202 
403 39 421 
120 350 435 
215 202 378 
487 217 456 
13 110 125 
423 248 328 
430 240 175 
202 443 378 
413 350 454 
278 228 360 
13 148 211 
429 49 36 
202 50 110 
211 353 406 
361 328 439 
17 169 113 
...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 8ms
memory: 44616kb

input:

2000
643 1871
689 23
1822 1443
1031 1027
1655 845
189 771
1561 498
19 1778
576 1080
904 717
1690 291
1387 1077
398 811
1310 1231
645 1291
480 927
330 170
1464 1057
1033 894
1308 288
1292 1529
1212 122
1108 401
89 1118
1058 1088
1764 1314
981 1255
1893 864
180 1887
1903 843
734 1412
883 1013
1739 124...

output:

1995 1000 418 
528 898 1026 
809 1000 1283 
870 831 1000 
692 1343 1533 
1285 1111 1118 
798 1262 1738 
1563 1991 727 
1277 270 1095 
98 1968 439 
29 692 1414 
464 413 195 
176 910 809 
89 572 1001 
664 572 722 
158 1533 174 
1001 1533 1343 
989 1991 735 
652 1950 1672 
1848 1279 1220 
1343 409 105 ...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 514ms
memory: 75812kb

input:

200000
56968 132021
105656 107536
123627 58349
119191 138198
133708 142638
114350 24980
137784 40346
124158 130204
80684 183207
78156 94449
21893 157560
54464 73571
145830 57756
160288 32120
178632 142663
26565 185985
70576 24906
32217 115826
185756 137673
54280 179613
77826 144447
66005 29955
11745...

output:

87763 127372 167377 

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 488ms
memory: 76052kb

input:

200000
41999 100683
85781 129266
122431 179332
162416 44814
24405 42267
154161 12483
178049 159964
67625 152391
133072 25866
178005 14695
94384 170290
54701 40323
66280 128515
159022 55057
14985 12920
182805 40659
173117 67973
99771 26102
198919 94543
23608 187601
61125 5759
89437 47647
18142 192402...

output:

82066 7276 199629 

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 502ms
memory: 76400kb

input:

200000
195072 75458
31991 127114
60943 49502
186375 1130
45394 147217
168455 84307
132752 188952
101108 130004
107490 22003
16275 187645
111002 42669
138880 137115
112688 172751
81697 99037
166996 18495
2234 56119
170807 101349
105736 23180
148159 40863
136678 11849
190707 91245
61779 120740
157115 ...

output:

34411 98198 27046 
39355 49857 70450 
52145 64637 69064 
47190 118391 172547 
39160 61668 93926 
47753 111291 33917 
86727 167090 151320 
187258 164457 118748 
88824 54873 116603 
197158 106757 196326 

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 488ms
memory: 75964kb

input:

200000
48556 78408
155026 9376
8983 61211
150393 85068
90892 109283
75746 89742
6760 187245
168658 130735
68602 127646
60802 149828
22898 59471
172845 100274
42303 190696
7612 134905
94702 59800
129633 192496
19903 64869
51318 63358
34692 66030
98535 176606
153647 177529
157903 147292
106273 107278
...

output:

160968 115648 3363 
156481 27494 156628 
3364 22086 157918 
126929 139436 4472 
147837 75665 40179 
31684 19769 84929 
77495 79528 148651 
49868 110284 99352 
12157 122489 51911 
142520 126427 172234 

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 593ms
memory: 139788kb

input:

200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

54356 200000 137052 
200000 170197 131241 
84517 200000 179296 
183330 163219 200000 
158370 200000 194345 
85385 171870 200000 
143829 200000 85216 
200000 122372 28132 
200000 25711 157674 
200000 179037 24813 
200000 197101 57460 
117928 178289 200000 
200000 179418 195973 
22762 116045 200000 
1...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 688ms
memory: 84116kb

input:

200000
5732 55198
128966 25317
114737 116391
150003 18274
43867 70745
76222 4169
55976 114951
198396 72896
38647 19711
12756 172119
73197 117994
117512 14177
130965 126990
119440 183341
142023 60829
111893 57350
122754 123305
36525 79077
36447 91967
135405 170456
165839 147481
66074 175822
22238 264...

output:

197325 197325 4704 
197325 197325 10591 
56264 56264 38396 
197325 197325 109303 
197325 197325 79504 
197325 197325 99289 
197325 197325 69799 
197325 197325 174490 
197325 197325 126621 
197325 197325 140463 
197325 197325 167534 
197325 197325 102608 
197325 197325 12754 
197325 197325 186281 
19...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 713ms
memory: 83852kb

input:

200000
185063 17064
180987 114492
88071 71803
158363 135918
60910 54848
97338 6734
192937 9410
49617 199068
82499 63554
188791 188152
178767 40866
11304 27212
144234 138097
42236 3946
103355 12683
50992 20598
145723 48620
11709 115688
123172 121379
70541 130844
147827 39431
139372 61280
42705 54015
...

output:

80587 34708 144003 
147087 81464 42045 
104657 112119 167698 
165046 74246 102483 
142619 34588 160376 
81857 53666 87450 
113149 177939 151070 
196768 112246 199684 
155312 21334 5823 
172100 54335 184300 
119888 20580 66285 
44224 98649 113772 
33460 133493 71093 
179652 37925 80938 
171545 129932...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 676ms
memory: 83664kb

input:

200000
197244 185999
18639 124754
154223 12099
53676 167616
22710 22294
150412 66132
19320 75478
170410 122661
130961 175554
171586 85572
188386 81238
120249 117687
43214 126266
8744 165654
164725 189519
124144 170329
86605 100197
130545 17030
113301 96665
67733 187286
37846 146399
75352 117550
3235...

output:

52953 115995 20019 
95761 156955 99574 
2614 160961 93061 
52821 146957 191755 
41838 63792 156254 
145651 155074 78456 
58258 144129 162505 
166586 3669 94060 
169597 31844 74478 
137988 168152 59440 
73735 106440 172760 
11066 19691 100001 
160854 8619 7976 
95660 185898 38381 
17492 146460 171987...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed