QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#105819	#6142. 宝石	zaneyu^#	5	4ms	18052kb	C++23	4.7kb	2023-05-15 16:36:50	2024-05-31 13:37:29

Judging History

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

[2024-05-31 13:37:29]
评测

测评结果：5
用时：4ms
内存：18052kb

查看

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-15 16:36:50]
提交

answer

/*input
7 3 3
2 3 1
2 1 3 3 2 1 3
1 2
2 3
1 4
4 5
4 6
6 7
5
3 5
1 3
7 3
5 7
7 5

*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?"\n":"");
    return out;
}
ll mult(ll a,ll b){
    return a*b%MOD;
}
ll mypow(ll a,ll b){
    a%=MOD;
    if(a==0) return 0;
    if(b<=0) return 1;
    ll res=1LL;  
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
int pu[maxn][18],pd[maxn][18];
int par[maxn][18];
int pos[maxn];
int arr[maxn];
vector<int> v[maxn];
vector<int> pv[maxn];
int dep[maxn];
int fon[maxn];
int n,m,c;
void dfs(int u,int p){
    par[u][0]=p;
    if(pos[u]!=-1) pv[pos[u]].pb(u);
    for(int x:v[u]){
        if(x==p) continue;
        dep[x]=dep[u]+1;
        dfs(x,u);
    }
    fon[u]=pv[1].back();
    if(pos[u]==-1) return;
    pu[u][0]=pv[pos[u]+1].back();
    pd[u][0]=pv[pos[u]-1].back();
    pv[pos[u]].pop_back();
}
int get(int a,int d){
    while(d){
        a=par[a][__lg(lowb(d))];
        d-=lowb(d);
    } 
    return a;
}
int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    a=get(a,dep[a]-dep[b]);
    if(a==b) return a;
    for(int j=17;j>=0;j--){
        if(par[a][j]!=par[b][j]){
            a=par[a][j],b=par[b][j];
        }
    }
    return par[a][0];
}
pii qr[maxn];
vector<int> qq[maxn];
pii rng[maxn];
void dfs2(int u,int p){
    if(pos[u]!=-1) pv[pos[u]].pb(u);
    for(int x:v[u]){
        if(x==p) continue;
        dfs2(x,u);
    }
    for(int x:qq[u]){
        int mid=(rng[x].f+rng[x].s+1)/2;
        int tp=qr[x].f,st=qr[x].s;
        int t=pv[mid].back();
        if(t!=-1){
            if(dep[t]>=dep[tp]) ++st;
            for(int j=17;j>=0;j--){
                if(pd[t][j]!=-1 and dep[pd[t][j]]>=dep[tp]){
                    st+=(1<<j);
                    t=pd[t][j];
                }
            }
        }

        if(st>=mid){
            rng[x].f=mid;
        }
        else{
            rng[x].s=mid-1;
        }
    }
    if(pos[u]==-1) return;
    pv[pos[u]].pop_back();
}
int pp[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,c;
    cin>>n>>m>>c;
    REP(i,m) pp[i]=-1;
    REP1(i,c){
        int x;
        cin>>x;
        --x;
        pp[x]=i;
    }
    REP(i,n){
        int x;
        cin>>x;
        --x;
        pos[i]=pp[x];
    }
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        --a,--b;
        v[a].pb(b),v[b].pb(a);
    }
    REP(i,c+3) pv[i].pb(-1);
    dfs(0,-1);
    REP1(j,17){
        REP(i,n){
            if(par[i][j-1]!=-1) par[i][j]=par[par[i][j-1]][j-1];
            else par[i][j]=-1;
            if(pu[i][j-1]!=-1) pu[i][j]=pu[pu[i][j-1]][j-1];
            else pu[i][j]=-1;
            if(pd[i][j-1]!=-1) pd[i][j]=pd[pd[i][j-1]][j-1];
            else pd[i][j]=-1;
        }
    }
    int q;
    cin>>q;
    REP(i,q){
        int s,t;
        cin>>s>>t;
        --s,--t;
        int z=lca(s,t);
        s=fon[s];
        int ans=0;
        if(s!=-1){
            if(dep[s]>dep[z]) ++ans;
            for(int j=17;j>=0;j--){
                if(par[s][j]!=-1 and dep[par[s][j]]>dep[z]){
                    s=par[s][j];
                    ans+=(1<<j);
                }
            }
        }
        qr[i]={z,ans};
        rng[i]={ans,c};
        qq[t].pb(i);
        //go frm z to t 
    }
    REP(asd,2){
        dfs2(0,-1);
    }
    REP(i,q){
        cout<<rng[i].f<<'\n';
    }
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 3ms

memory: 15968kb

input:

10 4 4
2 1 4 3
2 4 4 1 1 1 1 1 4 4
2 1
3 2
4 1
5 1
6 5
7 1
8 5
9 5
10 3
10
5 1
1 7
6 8
5 10
7 6
9 3
3 9
2 7
9 7
2 4

output:

result:

ok 10 numbers

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 13924kb

input:

10 4 4
1 3 2 4
3 4 4 3 1 3 1 2 4 2
2 1
3 1
4 2
5 2
6 4
7 6
8 5
9 2
10 4
10
2 8
6 9
1 6
9 8
4 9
2 8
4 6
3 10
7 8
1 10

output:

result:

wrong answer 9th numbers differ - expected: '3', found: '4'

Test #3:

score: 0

Wrong Answer

time: 4ms

memory: 16008kb

input:

1000 20 20
20 3 1 5 4 17 10 11 2 8 19 7 15 13 9 14 16 18 12 6
16 1 17 10 17 3 12 1 15 18 1 10 10 13 1 16 9 8 4 8 20 9 14 2 2 13 14 16 11 8 5 19 12 4 13 10 10 1 7 14 2 17 13 1 15 6 13 15 7 19 6 12 6 16 14 6 20 17 19 3 17 7 15 6 20 1 15 19 3 4 13 14 11 14 14 11 2 12 16 4 16 16 15 20 20 4 17 13 4 16 19...

output:

result:

wrong answer 4th numbers differ - expected: '1', found: '0'

Test #4:

score: 0

Wrong Answer

time: 0ms

memory: 11992kb

input:

1000 20 20
5 8 2 4 10 3 17 7 11 9 16 6 19 18 13 1 14 20 12 15
15 4 15 5 15 11 8 10 2 11 5 18 16 9 2 5 14 14 10 6 14 19 2 14 7 10 18 3 3 11 9 9 19 18 18 20 11 8 14 12 18 16 17 4 15 15 13 20 7 20 16 18 1 9 3 10 9 6 12 1 17 1 15 13 19 6 12 18 1 6 3 2 14 2 6 2 6 6 13 19 16 11 17 6 6 16 17 14 10 17 1 11 ...

output:

result:

wrong answer 1st numbers differ - expected: '1', found: '3'

Test #5:

score: 0

Wrong Answer

time: 4ms

memory: 18052kb

input:

1000 20 20
16 6 12 9 8 3 17 13 14 18 4 10 7 20 15 19 1 5 2 11
12 8 20 15 15 15 8 13 7 16 2 16 15 3 6 8 5 8 9 15 10 18 4 8 17 15 10 19 9 13 15 13 17 12 15 14 4 11 12 6 11 1 11 9 3 11 19 12 8 8 6 18 4 12 19 18 2 5 17 18 13 11 13 14 9 16 3 1 18 5 5 18 3 18 14 2 15 3 10 16 9 11 16 9 12 5 13 11 8 1 16 19...

output:

result:

wrong answer 2nd numbers differ - expected: '1', found: '2'

Test #6:

score: 0

Runtime Error

input:

200000 300 300
196 108 179 192 60 223 53 267 231 41 90 297 123 193 81 234 151 287 167 107 86 163 200 112 182 181 17 217 230 237 249 202 127 61 80 286 34 279 52 118 14 58 85 255 262 268 105 257 194 160 190 211 110 106 71 206 283 141 154 145 245 67 216 271 274 31 146 131 189 82 29 73 282 228 5 201 187...

output:

result:

Test #7:

score: 0

Runtime Error

input:

200000 300 300
295 274 12 146 252 147 282 178 187 13 35 278 199 11 134 165 229 172 261 244 238 202 118 245 124 209 26 228 190 5 149 141 132 107 184 175 121 283 114 15 101 60 173 158 243 289 91 263 160 50 240 31 194 49 36 102 34 96 130 98 248 55 6 223 46 272 213 182 1 164 144 224 279 14 82 256 106 23...

output:

result:

Test #8:

score: 0

Runtime Error

input:

200000 300 300
10 14 170 41 80 89 291 95 48 135 157 230 249 110 186 87 111 93 299 84 73 35 127 259 33 30 120 252 2 205 178 166 142 52 297 62 254 124 224 72 168 167 67 147 4 85 160 189 136 213 37 123 28 211 300 203 46 285 13 104 103 286 198 241 55 20 98 39 29 1 287 226 112 208 260 32 47 266 75 82 204...

output:

result:

Test #9:

score: 0

Runtime Error

input:

200000 300 300
135 142 98 181 82 176 67 7 257 203 299 27 102 265 215 178 12 147 31 218 36 253 138 290 70 159 78 20 95 96 54 58 40 293 240 150 13 143 97 275 37 4 187 146 89 126 112 127 38 144 157 15 109 206 124 33 177 23 233 6 268 270 101 274 50 191 61 287 99 87 259 115 196 118 229 3 25 48 134 24 28 ...

output:

result:

Test #10:

score: 0

Runtime Error

input:

200000 300 300
274 49 162 254 89 166 94 176 152 82 270 204 218 150 126 106 14 252 194 64 103 71 39 79 70 81 132 102 18 223 217 47 171 142 196 99 186 73 231 178 80 258 293 192 221 238 40 68 37 101 46 172 190 241 52 153 197 266 220 159 17 173 38 299 263 95 48 151 76 255 191 112 207 226 57 135 61 275 1...

output:

result:

Test #11:

score: 0

Runtime Error

input:

200000 20127 20127
18040 5063 1949 3575 2887 4151 1159 1395 9647 1376 16097 1422 9694 637 14090 9230 14318 13072 18802 7526 10464 4802 5645 5290 5964 12137 6076 13499 1318 13431 19198 9334 1530 14120 11039 15879 13900 16154 4761 9216 10424 9009 17705 9859 5950 3661 12576 7727 12666 3694 12659 11255 ...

output:

result:

Test #12:

score: 0

Runtime Error

input:

200000 23282 23282
21983 22037 20506 5857 14044 14669 3005 18638 11846 2997 11539 553 14415 19572 5331 4476 14759 12040 20064 7250 274 17286 11831 10626 7477 10762 6845 15046 12107 14685 18249 11525 2784 8792 17696 1632 23013 18350 2080 16516 16837 8455 17780 11515 18030 3775 18845 17393 21102 13274...

output:

result:

Test #13:

score: 0

Runtime Error

input:

200000 28544 28544
7244 5125 13001 24487 2244 14598 18685 18357 10046 22220 19562 8608 19790 17520 6216 14370 5433 26605 16988 9140 16226 26081 22437 5566 8245 14813 24444 28163 18528 2207 24794 12264 10635 5127 18902 19900 27203 26164 6846 6635 27305 1337 12224 16953 27055 12658 13986 1768 1176 192...

output:

result:

Test #14:

score: 0

Runtime Error

input:

200000 25120 25120
19718 16977 5459 6261 226 9358 19674 9257 20784 6657 3912 8494 14777 6941 9848 610 2913 20118 21634 14408 14166 22368 12192 12973 13467 4618 7443 8836 14545 14406 3814 24795 22415 13472 11011 16568 17540 8422 5328 13712 21752 18592 7878 24559 16275 21553 7342 11995 3001 16377 2430...

output:

result:

Test #15:

score: 0

Runtime Error

input:

200000 24328 24328
15195 1593 23225 20912 7763 20719 9202 1254 3290 17138 4223 14496 15571 18186 1033 8842 8522 20814 14920 18798 2047 6512 1982 4197 11481 23482 16371 17861 6280 6624 8117 10033 4398 23867 3528 6 2981 6944 7481 20962 21517 17989 23203 22361 1038 1246 13657 22894 2348 6730 7110 8880 ...

output:

result:

Test #16:

score: 0

Runtime Error

input:

200000 23535 23535
22853 557 15383 107 16780 17397 19383 23406 1069 14 9230 480 5190 10487 9042 19046 471 4135 19888 850 6067 62 14804 4650 2920 13459 14544 17662 16078 7574 21213 5405 1919 15140 7146 2925 4778 14951 15553 8580 6064 3892 11013 11012 2097 18893 7494 5195 12354 2651 11175 12606 12664 ...

output:

result:

Test #17:

score: 0

Runtime Error

input:

200000 22743 22743
26 4272 21333 3815 310 870 19582 21253 2000 1381 11577 19266 2640 22550 17985 5590 7197 6217 5104 4265 21673 3978 16073 21248 21987 13590 5409 19015 1944 21469 21370 6780 20746 13576 8195 11758 14166 15845 8397 10421 14501 22171 21406 10972 7967 14255 7357 5492 14937 17706 20760 1...

output:

result:

Test #18:

score: 0

Runtime Error

input:

200000 25897 25897
9229 3418 18627 21598 21258 18733 11907 14782 18543 17294 4540 18700 24910 13430 9782 9506 7390 2006 20953 3780 19408 18626 21687 19405 19781 12991 158 7068 23862 2769 22136 25319 13968 13880 24740 21463 21488 13464 15681 12433 24507 9218 20806 18559 6736 20446 13834 23123 24256 2...

output:

result:

Test #19:

score: 0

Runtime Error

input:

200000 23789 23789
17563 21148 9167 3895 16973 16113 9911 2518 4703 218 22930 284 16799 19632 16346 8224 2871 19891 2911 16600 6291 9116 21363 20129 5027 14959 3788 14003 15535 3755 22226 10930 13781 21835 12820 9609 18032 16716 503 10116 16382 10138 11039 21423 5390 8456 17993 7383 4331 4347 14717 ...

output:

result:

Test #20:

score: 0

Runtime Error

input:

200000 20366 20366
15031 14077 7945 19727 9442 11037 3781 14028 13750 13686 3985 17531 13107 605 9577 17785 10007 5565 2954 8868 3804 17501 1912 9811 5964 17853 16747 9194 14398 10970 8926 4950 5892 3292 18378 10549 8905 575 1906 6708 3449 1776 1494 9237 9873 17896 18498 15097 15870 6150 6842 18640 ...