QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297818 | #4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》 | Kevin5307 | 0 | 646ms | 175548kb | C++20 | 3.5kb | 2024-01-05 11:27:34 | 2024-01-05 11:27:34 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
vector<int> G[1001000];
int n;
ll a[1001000];
int depth[1001000];
int anc[20][1001000];
int mx[20][1001000];
int dfn[1001000],son[1001000],siz[1001000],tp[1001000],tot;
void dfs1(int u,int fa)
{
siz[u]=1;
depth[u]=depth[fa]+1;
// anc[0][u]=fa;
// mx[0][u]=a[u];
for(auto v:G[u])
if(v!=fa)
{
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int fa)
{
if(!tp[u]) tp[u]=u;
dfn[u]=++tot;
if(son[u])
{
tp[son[u]]=tp[u];
dfs2(son[u],u);
}
for(auto v:G[u])
if(v!=son[u]&&v!=fa)
dfs2(v,u);
}
ll b[1001000];
int range_max(int l,int r)
{
int x=__lg(r-l+1);
return (b[mx[x][l]]>b[mx[x][r-(1<<x)+1]])?mx[x][l]:mx[x][r-(1<<x)+1];
}
struct _comp_{const bool operator ()(const array<int,3> &a,const array<int,3> &b){return ::b[a[0]]>::b[b[0]];}};
#define count _count
int cnt[1001000],count;
int trans[1001000][2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
G[u].pb(v);
G[v].pb(u);
}
for(int i=1;i<=n;i++)
cin>>a[i];
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++)
b[dfn[i]]=a[i];
for(int i=1;i<=n;i++)
mx[0][i]=i;
for(int i=1;i<20;i++)
for(int j=1;j<=n;j++)
if(j+(1<<(i-1))<=n)
mx[i][j]=(b[mx[i-1][j]]>b[mx[i-1][j+(1<<(i-1))]])?mx[i-1][j]:mx[i-1][j+(1<<(i-1))];
else
mx[i][j]=mx[i-1][j];
int q;
cin>>q;
ll lstans=0;
while(q--)
{
int u,v,m;
ll a,b;
cin>>a>>b>>m;
u=(a^lstans)%n+1;
v=(b^lstans)%n+1;
priority_queue<array<int,3>,vector<array<int,3>>,_comp_> pq;
while(tp[u]!=tp[v])
{
if(depth[tp[u]]<depth[tp[v]]) swap(u,v);
pq.push({range_max(dfn[tp[u]],dfn[u]),dfn[tp[u]],dfn[u]});
u=anc[0][tp[u]];
}
if(dfn[u]>dfn[v]) swap(u,v);
pq.push({range_max(dfn[u],dfn[v]),dfn[u],dfn[v]});
vector<ll> vec;
while(sz(vec)<(m+1)*64&&!pq.empty())
{
array<int,3> arr=pq.top();
pq.pop();
vec.pb(::b[arr[0]]);
if(arr[0]!=arr[1])
pq.push({range_max(arr[1],arr[0]-1),arr[1],arr[0]-1});
if(arr[0]!=arr[2])
pq.push({range_max(arr[0]+1,arr[2]),arr[0]+1,arr[2]});
}
count=1;
for(auto val:vec)
{
int cur=1;
cnt[cur]++;
for(int i=61;i>=0;i--)
{
int c=val>>i&1;
if(!trans[cur][c]) trans[cur][c]=++count;
cur=trans[cur][c];
cnt[cur]++;
}
}
vector<int> cn;
ll ans=0;
cn.pb(1);
for(int i=61;i>=0;i--)
{
int sum=0;
for(auto nd:cn)
sum+=cnt[trans[nd][1]];
vector<int> ncn;
for(auto nd:cn)
if(trans[nd][1])
ncn.pb(trans[nd][1]);
if(sum<m)
{
for(auto nd:cn)
if(trans[nd][0])
ncn.pb(trans[nd][0]);
}
else
ans|=(1ll<<i);
swap(cn,ncn);
}
for(int i=1;i<=count;i++)
cnt[i]=trans[i][0]=trans[i][1]=0;
cout<<(lstans=ans)<<'\n';
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 3ms
memory: 79652kb
input:
931 184 700 485 184 419 485 386 419 308 386 114 308 301 114 598 301 120 598 144 120 595 144 812 595 236 812 7 236 543 7 327 543 858 327 68 858 177 68 398 177 899 398 408 899 848 408 202 848 269 202 304 269 540 304 647 540 672 647 314 672 157 314 241 157 745 241 300 745 343 300 92 343 117 92 30 117 2...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #2:
score: 0
Accepted
time: 0ms
memory: 79896kb
input:
915 911 748 514 911 805 514 729 805 753 729 40 753 671 40 664 671 94 664 61 94 726 61 690 726 597 690 216 597 644 216 533 644 605 533 22 605 307 22 455 307 377 455 114 377 660 114 589 660 569 589 409 569 408 409 821 408 736 821 599 736 60 599 475 60 57 475 412 57 85 412 524 85 846 524 595 846 262 59...
output:
288230376151711752
result:
ok 1 number(s): "288230376151711752"
Test #3:
score: 0
Accepted
time: 8ms
memory: 81728kb
input:
930 111 896 637 111 559 637 289 559 103 289 759 103 341 759 605 341 778 605 154 778 169 154 721 169 631 721 741 631 750 741 344 750 641 344 639 641 769 639 48 769 389 48 25 389 70 25 508 70 185 508 199 185 602 199 89 602 473 89 565 473 373 565 865 373 867 865 658 867 271 658 685 271 269 685 317 269 ...
output:
268435456
result:
ok 1 number(s): "268435456"
Test #4:
score: 0
Accepted
time: 3ms
memory: 79684kb
input:
948 537 716 933 537 605 933 563 605 801 563 860 801 19 860 717 19 908 717 820 908 885 820 693 885 69 693 263 69 129 263 295 129 880 295 303 880 12 303 299 12 1 299 421 1 312 421 720 312 100 720 438 100 380 438 386 380 223 386 627 223 293 627 387 293 709 387 193 709 640 193 906 640 34 906 405 34 790 ...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #5:
score: 0
Accepted
time: 3ms
memory: 78812kb
input:
928 626 381 247 626 97 247 358 97 886 358 898 886 736 898 776 736 75 776 123 75 512 123 223 512 355 223 530 355 95 530 523 95 903 523 144 903 324 144 382 324 487 382 127 487 538 127 171 538 836 171 129 836 259 129 914 259 574 914 7 574 141 7 246 141 65 246 482 65 865 482 265 865 690 265 925 690 449 ...
output:
134217728
result:
ok 1 number(s): "134217728"
Test #6:
score: 0
Accepted
time: 4ms
memory: 79100kb
input:
941 87 448 396 87 398 396 623 398 837 623 234 837 896 234 258 896 700 258 52 700 27 52 515 27 308 515 774 308 76 774 21 76 753 21 493 753 902 493 878 902 58 878 146 58 342 146 414 342 312 414 621 312 88 621 460 88 683 460 150 683 845 150 535 845 467 535 326 467 247 326 280 247 474 280 124 474 22 124...
output:
1152921504606846976
result:
ok 1 number(s): "1152921504606846976"
Test #7:
score: -5
Wrong Answer
time: 0ms
memory: 79384kb
input:
947 635 486 821 635 758 821 504 758 470 504 170 470 468 170 778 468 560 778 864 560 308 864 213 308 43 213 849 43 525 849 126 525 681 126 785 681 640 785 254 640 354 254 263 354 455 263 295 455 714 295 474 714 64 474 794 64 582 794 325 582 676 325 176 676 393 176 624 393 86 624 205 86 359 205 704 35...
output:
72057594037927936
result:
wrong answer 1st numbers differ - expected: '1152921504606846976', found: '72057594037927936'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 27ms
memory: 96524kb
input:
99115 98506 98914 1961 98506 45808 1961 23027 45808 16655 23027 66393 16655 77250 66393 68284 77250 53684 68284 21189 53684 84955 21189 73464 84955 47574 73464 40651 47574 21101 40651 6589 21101 59680 6589 6185 59680 25529 6185 207 25529 33286 207 98459 33286 92565 98459 85446 92565 97388 85446 1630...
output:
10
result:
wrong answer 1st numbers differ - expected: '2050', found: '10'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Wrong Answer
Test #45:
score: 0
Wrong Answer
time: 646ms
memory: 175548kb
input:
996678 2 1 3 1 4 1 5 1 6 3 7 5 8 5 9 5 10 7 11 8 12 9 13 1 14 2 15 7 16 4 17 5 18 17 19 16 20 2 21 1 22 1 23 9 24 17 25 19 26 10 27 9 28 7 29 25 30 25 31 4 32 11 33 31 34 21 35 13 36 19 37 25 38 10 39 11 40 20 41 35 42 1 43 19 44 20 45 41 46 1 47 19 48 5 49 28 50 21 51 33 52 7 53 14 54 21 55 20 56 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '4', found: '0'
Subtask #8:
score: 0
Skipped
Dependency #1:
0%