QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#933524 | #6340. Tourism | sunkaihuan | 0 | 411ms | 18988kb | C++14 | 2.2kb | 2025-03-13 19:59:00 | 2025-03-13 19:59:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct seg{
int l,r;mutable int v;
bool operator<(const seg &a)const{return l<a.l;}
};set<seg> s;
#define it set<seg>::iterator
vector<pair<int,int> > ql[N];
vector<int> to[N];
int fa[N],d[N],sz[N],son[N];
int dfn[N],tp[N],num;
int n,m,q,p[N],c[N],an[N];
void add(int x,int v){for(;x;x-=x&-x)c[x]+=v;}
int ask(int x){int r=0;for(;x<=n;x+=x&-x)r+=c[x];return r;}
void dfs1(int x,int f){
fa[x]=f,d[x]=d[f]+1,sz[x]=1;
for(auto j:to[x]){
if(j==f)continue;dfs1(j,x);
if(sz[son[x]]<sz[j])son[x]=j;
sz[x]+=sz[j];
}
}
void dfs2(int x,int f){
dfn[x]=++num,tp[x]=f;
if(son[x])dfs2(son[x],f);
for(auto j:to[x])
if(j!=fa[x]&&j!=son[x])dfs2(j,j);
}
it in(int l,int r,int w){add(w,r-l+1);return s.insert({l,r,w}).first;}
void de(int l,int r,int w){add(w,-r+l-1),s.erase({l,r,w});}
it split(int x){
it pl=s.lower_bound({x,-1,0});
if(pl!=s.end()&&pl->l==x)return pl;
pl--;if(pl->r<x)return s.end();
int l=pl->l,r=pl->r,v=pl->v;assert(l<x&&r>=x);
de(l,r,v);in(l,x-1,v);return in(x,r,v);
}
void ins(int l,int r,int w){
it itr=split(r+1),itl=split(l),t;
for(it pl=itl;pl!=itr;)t=pl,assert(t!=s.end()),pl++,de(t->l,t->r,t->v);
in(l,r,w);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m>>q; int x,y;
for(int i=1;i<n;i++)cin>>x>>y,
to[x].push_back(y),to[y].push_back(x);
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=m;i++)cin>>p[i];
for(int i=1;i<=q;i++)
cin>>x>>y,ql[y].push_back({x,i});s.insert({1,n,0});
for(int i=1;i<=m;i++){
if(i>1){
x=p[i-1],y=p[i];
while(tp[x]!=tp[y]){
if(d[tp[x]]<d[tp[y]])
ins(dfn[tp[y]],dfn[y],i),y=fa[tp[y]];
else ins(dfn[tp[x]],dfn[x],i-1),x=fa[tp[x]];
}if(d[x]<d[y])ins(dfn[x],dfn[y],i),p[i]=x;
else{
if(x!=y)ins(dfn[y]+1,dfn[x],i-1);
ins(dfn[y],dfn[y],i);p[i]=y;
}
}for(auto j:ql[i])
an[j.second]=(j.first==i?1:ask(j.first));
}for(int i=1;i<=q;i++)cout<<an[i]<<"\n";
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 11356kb
input:
166 249 224 158 52 52 82 158 36 117 158 119 117 5 82 158 18 22 36 82 143 105 36 22 152 36 92 117 2 123 158 5 134 119 89 31 119 92 48 105 149 149 17 108 31 134 50 3 52 63 158 3 51 42 22 17 10 103 158 50 122 92 85 50 78 117 159 36 20 143 115 158 83 20 4 142 22 23 3 96 10 19 134 8 10 151 92 65 108 89 5...
output:
67 39 110 93 110 139 0 27 126 121 70 97 83 96 25 113 86 60 0 49 107 131 66 33 9 0 86 110 60 123 46 130 73 0 93 0 113 85 25 95 127 69 85 121 77 127 123 83 34 0 99 121 63 59 99 106 0 69 127 51 74 134 0 94 27 120 105 116 36 30 124 112 130 0 34 112 138 0 98 39 122 109 1 105 137 73 105 109 89 95 31 120 1...
result:
wrong answer 2nd numbers differ - expected: '97', found: '39'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 49ms
memory: 18988kb
input:
55321 88650 75523 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
0 16 55316 55306 55319 54811 1 0 16 16 0 0 55318 1 55311 55311 87 0 0 55319 55319 55317 1 55319 0 55318 0 55318 16 16 55319 0 55319 1 16 16 16 16 16 0 1 0 16 55211 55204 0 55319 55319 55309 55318 16 55318 55319 0 55319 16 0 0 1 55319 55318 55318 55293 55319 1 55319 0 55317 16 55319 55319 1 0 55309 1...
result:
wrong answer 1st numbers differ - expected: '55319', found: '0'
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 154ms
memory: 15604kb
input:
54738 54525 1797 45211 4527 4527 43609 4527 19876 16325 43609 32183 4527 16325 32579 43609 25554 32183 38972 45211 53953 16325 19810 10881 19810 45211 12698 27967 19810 25554 46338 51894 45211 25388 16325 512 25554 43609 7820 10206 512 30021 32183 48647 43609 46338 44138 16766 7820 10023 53953 19810...
output:
276 239 199 215 294 241 233 267 184 241 208 241 257 226 216 222 192 270 221 242 287 226 216 252 273 204 282 187 259 195 154 185 207 242 218 205 241 233 195 240 259 245 269 339 224 206 242 202 261 276 174 243 178 229 251 243 239 231 204 250 278 215 203 170 244 258 210 307 232 232 211 224 249 256 204 ...
result:
wrong answer 2nd numbers differ - expected: '238', found: '239'
Subtask #5:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 411ms
memory: 18352kb
input:
55965 89652 95687 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26...
output:
42788 0 39914 18090 14936 32970 0 29300 18235 0 13086 21803 32163 16999 28245 2515 25805 13125 35238 21406 30989 5677 13902 35077 18388 21200 43577 0 0 12145 14861 0 12237 0 23259 11450 41924 20100 14626 41081 32139 2053 41166 24623 0 18786 29659 18499 42423 42321 30971 28924 0 25952 1194 16277 3802...
result:
wrong answer 2nd numbers differ - expected: '7820', found: '0'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%