QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408448 | #4814. Exciting Travel | chenxinyang2006 | WA | 2ms | 18252kb | C++20 | 3.2kb | 2024-05-10 12:26:08 | 2024-05-10 12:26:09 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int n,m;
int cnt;
int head[200005];
struct eg{
int to,nxt;
}edge[400005];
void make(int u,int v){
edge[++cnt].to = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
int N,fa[200005],siz[200005],dfn[200005],dep[200005],ST[20][200005];
inline int cmp(int x,int y){
if(dep[x] < dep[y]) return x;
return y;
}
inline int qry(int l,int r){
int x = __lg(r - l + 1);
return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}
inline int LCA(int u,int v){
if(u == v) return u;
u = dfn[u];v = dfn[v];
if(u > v) swap(u,v);
return fa[qry(u + 1,v)];
}
void dfs(int u,int f){
siz[u] = 1;
dfn[u] = ++N;
dep[u] = dep[f] + 1;
fa[u] = f;
ST[0][N] = u;
for(int i = head[u];i;i = edge[i].nxt){
int v = edge[i].to;
if(v == f) continue;
dfs(v,u);
siz[u] += siz[v];
}
}
int tree[200005];
#define lowbit(x) (x & (-x))
void upd(int pos,int C){
while(pos <= n){
tree[pos] += C;
pos += lowbit(pos);
}
}
int qry(int pos){
int res = 0;
while(pos){
res += tree[pos];
pos -= lowbit(pos);
}
return res;
}
int cov[200005];
void mdf(int u,int C){
upd(dfn[u],C);
if(dfn[u] + siz[u] <= n) upd(dfn[u] + siz[u],-C);
}
int chainsum(int u,int v,int d){
return qry(dfn[u]) + qry(dfn[v]) - 2 * qry(dfn[d]) + cov[d];
}
void cover(int u){
if(cov[u]) return;
cov[u] = 1;
mdf(u,1);
}
void dcover(int u){
if(!cov[u]) return;
cov[u] = 0;
mdf(u,-1);
}
int idx[200005];
struct path{
int u,v,d;
}S[200005];
bool cmp2(path p,path q){
return dep[p.d] > dep[q.d];
}
int solve(int k){
rep(i,1,k) cover(idx[i]);
rep(i,1,k - 1){
S[i].u = idx[i];S[i].v = idx[i + 1];S[i].d = LCA(idx[i],idx[i + 1]);
// printf("%d ",S[i].d);
}
// printf("\n");
sort(S + 1,S + k,cmp2);
int ans = 0;
rep(i,1,k - 1){
if(chainsum(S[i].u,S[i].v,S[i].d) == 2){
cover(S[i].d);
}else{
ans++;
}
}
rep(i,1,k) dcover(idx[i]);
rep(i,1,k - 1) dcover(S[i].d);
return ans;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,n - 1){
int u,v;
scanf("%d%d",&u,&v);
make(u,v);make(v,u);
}
dfs(1,0);
rep(i,1,17){
rep(j,1,n){
if(j + (1 << i) - 1 > n) break;
ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
}
}
rep(i,1,m){
int sz;
scanf("%d",&sz);
rep(j,1,sz) scanf("%d",&idx[j]);
printf("%d\n",solve(sz));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13984kb
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: 18196kb
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: 0ms
memory: 14104kb
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: 0ms
memory: 9952kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7888kb
input:
1 0
output:
result:
ok 0 number(s): ""
Test #6:
score: 0
Accepted
time: 0ms
memory: 14120kb
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: 2ms
memory: 14080kb
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: 14068kb
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: 2ms
memory: 18252kb
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 4 2 2 0 2 0 4 0 1 4 5 2 0 12 0 14 3 3 5 3 0 0 2 0 4 9 5 5 1 0 40 12 0 18 4 1 1 6 0 7 3 0 0 14 5 1 3 8 5 0 4 0 5 7 2 5 6 0 5 0 1 2 7 3 0 0 6 0 1 8 4 1 11 0 1 0 8 3 2 0 1 2 0 3 9 5 13 2 0 4 2 0 4 1 14 1 4 4 4 0 1 1 10 2 2 0 0 4 10 2 3 10 4 0 13 6 0 19 3 4 9 2 10 6 1 0 0 3 0 0 5 12 5 2 2 1 9 15...
result:
wrong answer 135th numbers differ - expected: '6', found: '5'