QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56906 | #4814. Exciting Travel | KING_UT# | WA | 8ms | 4324kb | C++20 | 5.9kb | 2022-10-21 20:40:49 | 2022-10-21 20:40:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define bg begin()
#define ed end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.bg,x.ed
#define si(x) (int)x.size()
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
template<class t,class u>bool chmin(t&a,u b){
if(a>b){a=b;return true;}
else return false;
}
template<class t,class u>bool chmax(t&a,u b){
if(a<b){a=b;return true;}
else return false;
}
template<class t>using vc=vector<t>;
template<class t>using vvc=vector<vector<t>>;
using vi=vc<int>;
using pi=pair<int,int>;
#define a first
#define b second
template<class E>
struct HLD{
vvc<E>g;
int n,rt,cnt;
vi sub,in,out,par,head,dep,hei,ni;
vvc<E>bin;
vc<E>pe;
int dfs1(int v,int p,int d){
par[v]=p;
dep[v]=d;
for(auto itr=g[v].begin();itr!=g[v].end();itr++)
if(*itr==p){
pe[v]=*itr;
g[v].erase(itr);
break;
}
for(auto &e:g[v]){
pe[e]=e;
sub[v]+=dfs1(e,v,d+1);
if(sub[g[v][0]]<sub[e]) swap(g[v][0],e);
}
return sub[v];
}
void dfs2(int v,int h){
in[v]=cnt++;
head[v]=h;
for(auto to:g[v])
dfs2(to,to==g[v][0]?h:to);
out[v]=cnt;
if(si(g[v])) hei[v]=hei[g[v][0]]+1;
}
HLD(){}
HLD(const vvc<E>&gg,int rr):g(gg),n(g.size()),rt(rr),cnt(0),
sub(n,1),in(n),out(n),par(n,-1),head(n),dep(n),hei(n,1),ni(n),
pe(n){
dfs1(rt,-1,0);
dfs2(rt,rt);
rep(i,n)ni[in[i]]=i;
bin.resize(20);
bin[0] = par;
rep(j, 19){
bin[j+1].resize(n);
rep(i, n){
if(bin[j][i]==-1) bin[j+1][i]=-1;
else bin[j+1][i]=bin[j][bin[j][i]];
}
}
}
int up(int v,int a){
rep(j, 20){
if(((a>>j)&1)) v = bin[j][v];
}
return v;
}
int lca(int a,int b){
while(head[a]!=head[b]){
if(dep[head[a]]>dep[head[b]]){
swap(a,b);
}
b=par[head[b]];
}
if(dep[a]>dep[b]) swap(a,b);
return a;
}
int len(int a,int b){
return dep[a]+dep[b]-dep[lca(a,b)]*2;
}
bool asde(int a,int b){
return in[a]<=in[b] and out[b]<=out[a];
}
vi index;
pair<vi,vc<pi>>tree_compress(vi vs){
if(index.size()==0) index.resize(n);
auto comp=[&](int x,int y){
return in[x]<in[y];
};
sort(vs.begin(), vs.end(), comp);
vs.erase(unique(vs.begin(), vs.end()),vs.end());
int k=vs.size();
rep(i,k-1){
vs.pb(lca(vs[i],vs[i+1]));
}
sort(vs.begin(), vs.end(), comp);
vs.erase(unique(vs.begin(), vs.end()),vs.end());
k=vs.size();
rep(i,k)index[vs[i]]=i;
vc<pi>es;
rng(i,1,k){
int p=lca(vs[i-1],vs[i]);
es.eb(i,index[p]);
}
return mp(vs, es);
}
};
struct BIT{
vc<int>b;
int sz;
void init(int a){
sz = a+3;
b.clear();
b.assign(sz, 0);
}
void add(int i, int v){
i ++;
for(;i<sz;i+=i&-i) b[i] += v;
}
int sum(int i){
i ++;
int ret=0;
for(;i;i-=i&-i) ret += b[i];
return ret;
}
}bit;
using P=pi;
int sol(vc<int>A, vc<int>info, vc<pi>edge){
unordered_map<int,int>M;
rep(i, A.size()){
M[A[i]] = i;
}
int n = A.size();
vc<int>imp(n);
for(auto v:info) imp[M[v]] = 1;
vvc<int>g; g.resize(n);
for(auto uv:edge){
g[uv.a].pb(uv.b);
g[uv.b].pb(uv.a);
}
HLD<int>h2(g, 0);
vc<int>sum2(n);
auto dfs0=[&](int v,int u,auto dfs0)->void{
sum2[v] += imp[v];
for(auto to:g[v]){
if(to==u)continue;
sum2[to] = sum2[v];
dfs0(to,v,dfs0);
}
};
dfs0(0,-1,dfs0);
//for(auto x:A) cout << x << " "; cout << endl;
//for(auto x:info) cout << x << " "; cout << endl;
//for(auto x:edge) cout << x.a << " " << x.b << endl;
//rep(i, n) cout << sum2[i] << " "; cout << endl;
vvc<P>q; q.resize(n);
int pre=0;
rng(i, 1, info.size()){
int u = M[info[i-1]];
int v = M[info[i]];
int w = h2.lca(u, v);
if(sum2[u]+sum2[v]-sum2[w]*2+imp[w] != 2) continue;
//cerr<<info[i-1]<<" "<<info[i]<<endl;
int L = h2.len(u, v);
if(L == 1) pre++;
else if(L == 2){
int mid;
if(u != w) mid=(h2.up(u, 1));
else mid=(h2.up(v, 1));
q[mid].eb(mid, mid);
}
else{
int mid1, mid2;
if(u != w) mid1=(h2.up(u, 1));
else mid1=(h2.up(v, L-1));
if(v != w) mid2=(h2.up(v, 1));
else mid2=(h2.up(u, L-1));
q[h2.lca(mid1, mid2)].eb(mid1, mid2);
}
}
bit.init(n+1);
vc<int>sum(n), dp(n);
auto dfs=[&](int v, int u, auto dfs) -> void{
for(auto to:g[v]){
if(to == u) continue;
dfs(to, v, dfs);
sum[v] += dp[to];
}
dp[v] = sum[v];
for(auto edd:q[v]){
int tmp=1;
int x[2]={edd.a, edd.b};
rep(_, 2){
int p = x[_];
if(p == v) continue;
int L = h2.len(p, v);
int ch = h2.up(p, L-1);
tmp += sum[ch]-dp[ch];
if(L > 1){
tmp += bit.sum(h2.in[p]);
tmp -= bit.sum(h2.in[ch]);
}
}
if(dp[v] < sum[v]+tmp) dp[v] = sum[v]+tmp;
}
bit.add(h2.in[v], sum[v]-dp[v]);
bit.add(h2.out[v], sum[v]-dp[v]);
};
dfs(0, -1, dfs);
return dp[0]+pre;
}
void slv(){
int n,m;
cin>>n>>m;
vvc<int>g; g.resize(n);
rep(i,n-1){
int u,v;cin>>u>>v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
}
HLD<int>h1(g, 0);
rep(_, m){
int k; cin >> k;
vc<int>vec(k);
rep(i, k) cin >> vec[i];
if(k <= 2){
cout << 0 << '\n';
continue;
}
rep(i, k) vec[i]--;
vc<int>A = vec;
rep(i, k-1){
int u = vec[i];
int v = vec[i+1];
int L = h1.len(u, v);
if(L == 1) continue;
else if(L == 2){
int w = h1.lca(u, v);
if(u != w) A.pb(h1.up(u, 1));
else A.pb(h1.up(v, 1));
}
else{
int w = h1.lca(u, v);
if(u != w) A.pb(h1.up(u, 1));
else A.pb(h1.up(v, L-1));
//cout<<u<<" "<<v<<endl;
//cout<<A.back()<<" ";
if(v != w) A.pb(h1.up(v, 1));
else A.pb(h1.up(u, L-1));
//cout<<A.back()<<endl;
//cout<<"_____"<<endl;
}
}
//for(auto a:A) cout<<a<<" ";cout<<endl;
auto ret = h1.tree_compress(A);
//for(auto a:ret.a) cout<<a<<" ";cout<<endl;
//for(auto b:ret.b) cout<<b.a<<" "<<b.b<<endl;
cout << k-1-sol(ret.a, vec, ret.b) << '\n';
}
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int t;t=1;//cin>>t;
while(t--) slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3672kb
input:
5 3 1 2 1 3 2 4 2 5 3 1 4 5 4 1 2 4 3 4 2 4 5 1
output:
1 1 2
result:
ok 3 number(s): "1 1 2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
8 7 1 2 1 3 1 4 2 5 2 6 5 7 3 8 1 4 2 1 7 3 5 2 4 4 3 6 1 4 6 5 3 7 1 2 4 6 4 8 3 5 6 1 7 2 8 5 4 6 1 3
output:
0 0 0 1 4 3 5
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
10 10 8 3 10 4 1 2 10 9 9 1 4 8 1 5 6 3 2 7 1 10 1 3 5 4 6 8 3 10 5 1 6 3 8 7 1 5 4 3 8 1 4 1 10 3 4 6 9 1 6 3 7 5 3
output:
0 0 3 2 0 1 0 1 0 1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #6:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
20 15 9 4 3 9 10 9 7 14 2 1 16 13 15 20 6 1 8 11 18 19 20 3 12 7 9 17 7 13 8 5 19 20 10 12 1 8 9 8 3 8 12 15 2 5 4 6 17 4 8 7 5 18 1 7 1 18 2 2 20 5 13 6 5 15 17 1 6 1 9 7 4 15 3 2 9 5 13 2 16 18 2 2 6 2 5 17 8 1 11 8 12 9 18 13 17 7 5 6 13 1 11 18 9
output:
1 0 4 0 0 0 2 0 0 4 0 0 0 4 4
result:
ok 15 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
20 15 15 2 4 12 6 3 20 16 7 15 6 14 13 10 11 20 3 9 13 4 5 19 1 14 5 7 18 9 18 8 17 12 8 2 11 19 17 1 2 3 11 5 9 11 14 20 3 4 9 11 13 4 6 18 6 5 16 7 17 2 2 14 1 11 2 9 3 1 10 2 17 8 1 8 1 16 6 13 17 10 2 4 3 7 2 3 7 6 15 9 17 3 14 3 10 7 9 19 4 2 20 8 11
output:
0 3 1 3 0 0 0 0 0 0 0 5 6 1 6
result:
ok 15 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
20 15 9 5 5 7 5 13 5 10 5 19 17 5 5 2 5 3 16 5 5 11 5 1 8 5 5 18 15 5 5 20 4 5 5 12 5 6 14 5 3 4 13 7 3 8 6 5 1 12 4 3 19 20 6 8 14 7 19 17 18 12 13 11 5 13 15 10 2 1 2 10 4 1 18 1 2 1 6 9 7 18 9 8 16 3 1 10 14 2 2 15 2 2 20 7 4 13 15 7 3 9 14 1 19
output:
1 1 0 2 6 3 0 0 0 0 7 0 0 5 0
result:
ok 15 numbers
Test #9:
score: -100
Wrong Answer
time: 8ms
memory: 4324kb
input:
1000 500 685 415 28 527 771 396 201 538 604 162 631 66 144 596 788 378 919 59 737 550 471 413 3 590 891 52 886 705 350 238 164 224 554 358 909 150 354 441 310 756 380 661 380 867 601 318 197 204 993 673 118 624 249 539 841 737 742 853 250 566 543 663 981 243 60 120 976 801 750 2 694 8 935 831 381 48...
output:
0 3 0 3 5 3 3 0 2 0 4 0 1 5 6 2 0 14 0 14 4 3 6 3 0 0 3 0 4 9 5 5 1 0 41 13 0 19 4 2 1 6 0 7 3 0 0 14 5 1 3 8 6 0 5 0 6 7 2 6 6 0 5 0 2 2 7 3 0 0 7 0 1 9 5 1 11 0 1 0 8 3 3 0 1 2 0 3 9 5 13 2 0 5 2 0 5 1 14 1 4 4 4 0 1 1 10 2 2 0 0 6 10 2 4 12 4 0 13 7 0 20 4 5 9 2 11 7 1 0 0 3 0 0 7 13 5 2 2 1 9 16...
result:
wrong answer 5th numbers differ - expected: '4', found: '5'