QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297815 | #4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》 | Kevin5307 | 15 | 1271ms | 254052kb | C++20 | 4.0kb | 2024-01-05 11:20:57 | 2024-01-05 11:20:57 |
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);
}
int lca(int u,int v)
{
for(int i=19;i>=0;i--)
{
if(depth[anc[i][u]]>=depth[v])
u=anc[i][u];
if(depth[anc[i][v]]>=depth[u])
v=anc[i][v];
}
if(u==v) return u;
for(int i=19;i>=0;i--)
if(anc[i][u]!=anc[i][v])
{
u=anc[i][u];
v=anc[i][v];
}
return anc[0][u];
}
bool check(int u,int v)
{
int d=depth[u]-depth[v];
if(d<0) return false;
for(int i=0;i<20;i++)
if(d>>i&1)
u=anc[i][u];
return u==v;
}
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];
for(int i=1;i<20;i++)
for(int j=1;j<=n;j++)
anc[i][j]=anc[i-1][anc[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*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: 0ms
memory: 120612kb
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: -5
Wrong Answer
time: 10ms
memory: 120344kb
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:
288230376151711744
result:
wrong answer 1st numbers differ - expected: '288230376151711752', found: '288230376151711744'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 32ms
memory: 147964kb
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: 15
Accepted
Test #45:
score: 15
Accepted
time: 1271ms
memory: 253380kb
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:
4 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 8 0 0 0 0 16 0 0 4096 0 0 0 0 4096 0 0 0 0 2 0 0 0 0 4 0 0 0 0 32 64 0 0 0 512 64 4 4096 0 2 0 0 131072 0 0 0 0 0 0 0 0 2 0 0 0 2 0 4096 2 0 0 0 0 0 512 2 8 0 0 4096 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 512 0 0 36 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 99210 numbers
Test #46:
score: 0
Accepted
time: 1229ms
memory: 254052kb
input:
992539 2 1 3 1 4 3 5 2 6 3 7 1 8 1 9 4 10 7 11 1 12 5 13 5 14 4 15 7 16 7 17 9 18 12 19 5 20 15 21 1 22 13 23 6 24 4 25 7 26 21 27 23 28 11 29 7 30 23 31 16 32 4 33 25 34 12 35 27 36 34 37 1 38 3 39 1 40 4 41 16 42 4 43 19 44 1 45 29 46 5 47 15 48 13 49 1 50 26 51 46 52 8 53 9 54 1 55 47 56 26 57 31...
output:
0 0 4096 2 0 0 8 0 0 16 0 0 0 0 0 128 0 532 2 640 0 16384 514 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2 0 0 2 0 128 0 0 0 2 0 0 2 0 128 0 0 0 0 132 2 0 0 0 0 128 0 4 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 128 0 256 0 0 0 0 0 0 0 0 16 2 0 2 0 0 0 264 0 0 0 0 0 0 0 0 0 2 0 0 4 5...
result:
ok 99668 numbers
Test #47:
score: 0
Accepted
time: 1267ms
memory: 253536kb
input:
991690 2 1 3 1 4 1 5 1 6 1 7 4 8 1 9 3 10 4 11 5 12 1 13 5 14 9 15 8 16 1 17 10 18 12 19 7 20 9 21 14 22 2 23 12 24 14 25 1 26 9 27 11 28 19 29 7 30 28 31 16 32 28 33 17 34 12 35 27 36 7 37 17 38 1 39 25 40 4 41 29 42 33 43 31 44 18 45 11 46 27 47 29 48 2 49 45 50 7 51 15 52 46 53 11 54 51 55 6 56 1...
output:
0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 1024 0 0 0 256 0 2 0 0 131104 0 0 131104 2 0 1024 0 0 0 258 0 0 16388 0 0 0 256 0 0 0 0 2 2 0 32 0 0 0 16384 0 0 32 4 0 0 2 0 0 0 2 0 0 1026 8 0 8 4 0 4 2 0 0 0 0 0 1024 0 2 0 36 0 2 0 4 0 32 0 2 2 0 8192 0 0 0 0 0 0 0 4098 0 0 0 0 0 32 4098 1024 0 2 2 0 0 0 4 4096 ...
result:
ok 99396 numbers
Test #48:
score: 0
Accepted
time: 1229ms
memory: 253500kb
input:
997182 2 1 3 1 4 2 5 1 6 5 7 1 8 2 9 5 10 1 11 6 12 3 13 5 14 3 15 11 16 1 17 9 18 2 19 1 20 7 21 5 22 2 23 15 24 13 25 21 26 1 27 2 28 3 29 19 30 20 31 4 32 19 33 16 34 23 35 13 36 13 37 14 38 33 39 13 40 25 41 15 42 32 43 34 44 40 45 13 46 41 47 46 48 32 49 29 50 39 51 2 52 16 53 41 54 3 55 7 56 1...
output:
0 0 0 0 0 0 4 0 4096 1024 0 4 0 16 64 8 0 0 0 0 1024 0 0 0 0 256 0 0 0 0 8192 0 0 1028 0 4 4 0 0 0 0 0 0 0 1024 0 0 0 16 0 0 2 0 0 0 0 0 0 0 4 0 64 4 0 524288 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 4096 1024 0 0 0 0 0 2 0 0 8 0 16 0 0 0 96 64 64 0 0 0 2 64 0 0 66 0 2 0 4096 0 0 0 2 64 0 0 0 0 2 0 0 256 0 0 ...
result:
ok 99733 numbers
Subtask #8:
score: 0
Skipped
Dependency #1:
0%