QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#297816#4909. 《关于因为与去年互测zjk撞题而不得不改题这回事》Crying0 885ms176064kbC++173.0kb2024-01-05 11:21:342024-01-05 11:21:35

Judging History

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

  • [2024-01-05 11:21:35]
  • 评测
  • 测评结果:0
  • 用时:885ms
  • 内存:176064kb
  • [2024-01-05 11:21:34]
  • 提交

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%