QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#461619 | #6340. Tourism | Rafi22# | 0 | 43ms | 15184kb | C++20 | 3.8kb | 2024-07-02 20:48:26 | 2024-07-02 20:48:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define ll long long
#define pb push_back
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
#define endl '\n'
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=998244353;
const int N=100007,S=300,pot=1<<17,LG=17;
int seg[2*pot+7];
int seg1[2*pot+7];
int que(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg[v];
if(r<a||l>b) return inf;
return min(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
int que1(int v,int a,int b,int l,int r)
{
if(a<=l&&b>=r) return seg1[v];
if(r<a||l>b) return -inf;
return max(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
}
vector<pair<int,int>>W[N];
int BIT[N];
void ins(int v)
{
for(;v<N;v+=v&-v) BIT[v]++;
}
int QUE(int v)
{
int res=0;
for(;v>0;v-=v&-v) res+=BIT[v];
return res;
}
struct Z
{
int l,r,i;
};
bool cmp(Z a,Z b)
{
if(a.l/S==b.l/S) return a.r<b.r;
else return a.l<b.l;
}
vector<int>G[N];
int ile[N];
int c[N];
int res[N];
int pre[N],post[N],cc;
int ord[N];
int d[N];
int xd[N];
int skok[N][LG];
void dfs(int v,int o)
{
pre[v]=++cc;
ord[cc]=v;
skok[v][0]=o;
FOR(i,1,LG-1) skok[v][i]=skok[skok[v][i-1]][i-1];
for(auto u:G[v])
{
if(u==o) continue;
d[u]=d[v]+1;
dfs(u,v);
}
post[v]=cc;
xd[pre[v]]=post[v];
}
bool anc(int u,int v)
{
return pre[u]<=pre[v]&&post[u]>=post[v];
}
int lca(int u,int v)
{
if(anc(u,v)) return u;
ROF(i,LG-1,0) if(!anc(skok[u][i],v)) u=skok[u][i];
debug("lca",u,v,skok[u][0]);
return skok[u][0];
}
int ans;
set<int>SS;
void add(int v)
{
debug("add",v);
if(sz(SS)>2)
{
int D=-inf;
set<int>::iterator it=SS.lower_bound(pre[v]);
if(*it!=inf)
{
int l=lca(v,ord[*it]);
D=max(D,d[l]);
}
it--;
if(*it!=-inf)
{
int l=lca(v,ord[*it]);
D=max(D,d[l]);
}
debug(d[v]-D);
ans+=d[v]-D;
}
else ans+=d[v]+1;
SS.insert(pre[v]);
}
void del(int v)
{
debug("del",v);
SS.erase(pre[v]);
if(sz(SS)>2)
{
int D=-inf;
set<int>::iterator it=SS.lower_bound(pre[v]);
if(*it!=inf)
{
int l=lca(v,ord[*it]);
D=max(D,d[l]);
}
it--;
if(*it!=-inf)
{
int l=lca(v,ord[*it]);
D=max(D,d[l]);
}
ans-=d[v]-D;
}
else ans-=d[v]+1;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
FOR(i,1,n-1)
{
int a,b;
cin>>a>>b;
G[a].pb(b);
G[b].pb(a);
}
dfs(1,1);
FOR(i,1,2*pot)
{
seg[i]=inf;
seg1[i]=-inf;
}
for(int i=1;i<=m;i++)
{
cin>>c[i];
seg[i+pot-1]=pre[c[i]];
seg1[i+pot-1]=pre[c[i]];
}
for(int i=pot-1;i>0;i--)
{
seg[i]=min(seg[2*i],seg[2*i+1]);
seg1[i]=max(seg1[2*i],seg1[2*i+1]);
}
vector<Z>Q;
FOR(i,1,q)
{
int l,r;
cin>>l>>r;
Q.pb({l,r,i});
int L=que(1,l,r,1,pot),R=que1(1,l,r,1,pot);
W[L].pb({R,i});
}
sort(all(Q),cmp);
int L=1,R=0;
SS.insert(inf);
SS.insert(-inf);
for(auto x:Q)
{
debug("Q",x.l,x.r);
while(L<x.l)
{
del(c[L]);
L++;
}
while(L>x.l)
{
L--;
add(c[L]);
}
while(R>x.r)
{
del(c[R]);
R--;
}
while(R<x.r)
{
R++;
add(c[R]);
}
res[x.i]=ans;
}
FOR(i,1,n)
{
if(i>1) ins(xd[i]);
for(auto [j,k]:W[i]) res[k]-=QUE(n)-QUE(j-1);
}
FOR(i,1,q) cout<<res[i]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 8312kb
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:
-48 -1852 -727 -40 -90 -2660 -3035 -130 -856 -1335 -87 -1491 -689 -37 25 -211 -29 -70 -3047 -148 -1489 -2863 -49 -165 -768 -3118 -892 -719 -787 -2355 -77 -1410 -42 -3084 -337 -1887 -857 -48 -98 -262 -1163 -51 -271 -899 -927 -855 -1502 -1099 -81 -3076 -219 -466 -49 -433 -738 -1434 -1960 -56 -1709 -35...
result:
wrong answer 1st numbers differ - expected: '67', found: '-48'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #56:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 43ms
memory: 15184kb
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 238 198 214 294 240 233 266 184 241 207 241 256 225 215 222 190 269 221 242 287 225 215 252 273 203 281 186 259 195 152 183 206 241 218 205 241 233 194 239 258 244 267 339 224 205 242 202 260 275 173 243 178 228 251 242 239 231 203 249 277 215 202 169 243 258 208 306 232 231 211 224 249 256 203 ...
result:
wrong answer 104th numbers differ - expected: '281', found: '270'
Subtask #5:
score: 0
Time Limit Exceeded
Test #102:
score: 0
Time Limit Exceeded
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:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%