QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#297816 | #4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》 | Crying | 0 | 885ms | 176064kb | C++17 | 3.0kb | 2024-01-05 11:21:34 | 2024-01-05 11:21:35 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 1e6+10,MAXM = 1000;
int n,q;
ll a[MAXN];
vector<int>e[MAXN];
int dfn[MAXN],ord[MAXN],sz[MAXN],son[MAXN],dep[MAXN],top[MAXN],fa[MAXN],dtot;
int now;
void dfs1(int u){
sz[u] = 1;
for(auto v : e[u])if(v ^ fa[u]){
dep[v] = dep[u]+1;
fa[v] = u;
dfs1(v);
if(sz[son[u]] < sz[v])son[u] = v;
sz[u] += sz[v];
}
}
void dfs2(int u,int node){
top[u] = node,dfn[u] = ++dtot,ord[dtot] = u;
if(son[u])dfs2(son[u],node);
for(auto v : e[u])if(v != fa[u] && v != son[u])dfs2(v,v);
}
namespace _{ //O(1) 区间min
int st[20][MAXN];
int cmp(int x,int y){return (a[x] > a[y]) ? (x) : (y);}
void solve(){
rep(i,1,n)st[0][i] = ord[i];
rep(j,1,19)rep(i,1,n-(1<<j)+1)st[j][i] = cmp(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int query(int x,int y){
int len = __lg(y-x+1);
return cmp(st[len][x],st[len][y-(1<<len)+1]);
}
};
using _::query;
ll lst;
int pL[MAXN],pR[MAXN];
typedef array<ll,2> pr; //(val,id)
priority_queue<pr> pq;
ll b[MAXM],tot;
void push(int L,int R,int t=0){
int id = query(L,R);
pL[dfn[id]] = L,pR[dfn[id]] = R;
if(!t)pq.push({a[id],id});
}
mt19937 rnd(time(NULL));
void solve(int x,int y,int m){
while(pq.size())pq.pop(); tot = 0;
int cnt = (m-1) * 63;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x,y);
push(dfn[top[x]],dfn[x]);
x = fa[top[x]];
now++;
}
if(dep[x] > dep[y])swap(x,y);
push(dfn[x],dfn[y]);
while(pq.size() && cnt--){
pr now = pq.top(); pq.pop();
b[++tot] = now[0];
int p = dfn[now[1]],u = pL[p],v = pR[p];
if(p != u)push(u,p-1);
if(p != v)push(p+1,v);
}
lst = 0;
if(tot >= m){
per(i,61,0){
lst ^= (1LL<<i);
int cnt = 0;
rep(j,1,tot)cnt += (b[j] & lst) == lst;
if(cnt < m){
lst ^= (1LL<<i);
}
}
}
cout<<lst<<"\n";
}
int main(){
//freopen("query.in","r",stdin);
//freopen("query.out","w",stdout);
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
rep(i,1,n-1){
int u,v; cin>>u>>v;
e[u].push_back(v); e[v].push_back(u);
}
rep(i,1,n)cin>>a[i];
dfs1(1);
dfs2(1,1);
_::solve();
cin>>q;
rep(i,1,q){
ll x,y,m; cin>>x>>y>>m;
x = (x^lst)%n+1;
y = (y^lst)%n+1;
solve(x,y,m);
}
cout<<"now : "<<now<<"\n";
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 27196kb
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 now : 1
result:
wrong output format Expected integer, but "now" found
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 25ms
memory: 45516kb
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:
2050 now : 0
result:
wrong output format Expected integer, but "now" found
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: 885ms
memory: 176064kb
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:
wrong output format Expected integer, but "now" found
Subtask #8:
score: 0
Skipped
Dependency #1:
0%