QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462771 | #6340. Tourism | Rafi22 | 0 | 752ms | 21516kb | C++20 | 3.2kb | 2024-07-04 03:46:56 | 2024-07-04 03:46:56 |
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=1000000007;
const int N=100007,L=17;
vector<int>G[N];
int s[N];
int c[N];
int ans[N];
vector<pair<int,int>>Q[N];
int pre[N],post[N],cc;
int skok[N][L];
int O[N];
void dfs(int v,int o)
{
pre[v]=++cc;
s[v]=1;
skok[v][0]=o;
O[v]=o;
FOR(i,1,L-1) skok[v][i]=skok[skok[v][i-1]][i-1];
for(auto u:G[v])
{
if(u==o) continue;
dfs(u,v);
s[v]+=s[u];
}
post[v]=cc;
}
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,L-1,0) if(!anc(skok[u][i],v)) u=skok[u][i];
return skok[u][0];
}
int head[N],pos[N],it;
void dfs1(int v,int o)
{
pos[v]=++it;
int mx=0,p=-1;
for(auto u:G[v])
{
if(u==o) continue;
if(s[u]>mx)
{
mx=s[u];
p=u;
}
}
if(p==-1) return ;
head[p]=head[v];
dfs1(p,v);
for(auto u:G[v])
{
if(u==o||u==p) continue;
head[u]=u;
dfs1(u,v);
}
}
int BIT[N];
void ins(int v,int x)
{
for(;v<N;v+=v&-v) BIT[v]+=x;
}
int que(int v)
{
int res=0;
for(;v>0;v-=v&-v) res+=BIT[v];
return res;
}
set<pair<pair<int,int>,int>>S;
void upd(int l,int r,int x)
{
if(l>r) return ;
debug(S);
debug(l,r,x);
vector<pair<pair<int,int>,int>>X;
X.pb({{r,l},x});
while(true)
{
pair<pair<int,int>,int>p=*S.lower_bound({{l,0},0});
if(p.st.nd>r) break;
debug(p.st.nd,p.st.st,p.nd);
S.erase(p);
ins(p.nd,-(p.st.st-p.st.nd+1));
if(p.st.nd<l) X.pb({{l-1,p.st.nd},p.nd});
if(p.st.st>r) X.pb({{p.st.st,r+1},p.nd});
}
for(auto t:X)
{
S.insert(t);
ins(t.nd,t.st.st-t.st.nd+1);
}
}
void path(int u,int v,int x)
{
int l=lca(u,v);
debug(u,v,l);
while(true)
{
if(pos[head[u]]>pos[l]) upd(pos[head[u]],pos[u],x);
else
{
upd(pos[l]+1,pos[u],x);
break;
}
u=O[head[u]];
}
while(true)
{
if(pos[head[v]]>pos[l]) upd(pos[head[v]],pos[v],x);
else
{
upd(pos[l]+1,pos[v],x);
break;
}
v=O[head[v]];
}
upd(pos[l],pos[l],x);
}
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);
head[1]=1;
dfs1(1,1);
FOR(i,1,m) cin>>c[i];
FOR(i,1,q)
{
int l,r;
cin>>l>>r;
if(l==r) ans[i]=1;
else Q[r].pb({l,i});
}
S.insert({{n,1},1});
ins(1,n);
S.insert({{0,0},0});
S.insert({{n+1,n+1},0});
FOR(i,2,m)
{
path(c[i-1],c[i],i);
cout<<i<<endl;
for(auto [l,j]:Q[i]) ans[j]=n-que(l);
}
FOR(i,1,q) cout<<ans[i]<<endl;
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5996kb
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:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
wrong answer 1st numbers differ - expected: '67', found: '2'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 173ms
memory: 21488kb
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:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
wrong answer 1st numbers differ - expected: '55319', found: '2'
Subtask #4:
score: 0
Wrong Answer
Test #69:
score: 0
Wrong Answer
time: 301ms
memory: 17780kb
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:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
wrong answer 1st numbers differ - expected: '276', found: '2'
Subtask #5:
score: 0
Wrong Answer
Test #102:
score: 0
Wrong Answer
time: 752ms
memory: 21516kb
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:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 10...
result:
wrong answer 1st numbers differ - expected: '42788', found: '2'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%