QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#325852 | #5580. Branch Manager | ngungu46 | WA | 143ms | 34116kb | C++14 | 1.6kb | 2024-02-12 01:35:36 | 2024-02-12 01:35:38 |
Judging History
answer
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 200005
int n, m;
int tin[MAX], tout[MAX];
int up[MAX][25];
int timer;
int l;
void dfs(int v, int p, vector<vector<int> > &graph){
timer++;
tin[v] = timer;
up[v][0] = p;
for(int i = 0; i <= l; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
for(int u: graph[v]){
if(u!=p) dfs(u, v, graph);
}
timer++;
tout[v] = timer;
}
bool is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_ancestor(u, v)){
return u;
}
if(is_ancestor(v, u)) return v;
for(int i = l; i>=0; i--){
if(!is_ancestor(up[u][i], v)) u = up[u][i];
}
return u;
}
int main(){
cin >> n >> m;
vector<vector<int> > graph(n+1);
for(int i = 1; i <= n-1; i++){
int x, y;
cin >> x >> y;
x--, y--;
graph[x].push_back(y);
}
for(auto v: graph){
sort(v.begin(), v.end());
}
l = ceil(log2(n));
timer = 1;
dfs(0, 0, graph);
int res = 1;
vector<int> ppl;
int p;
for(int i = 0; i < m; i++){
cin >> p;
p--;
ppl.push_back(p);
}
for(int i = 0; i < m-1; i++){
int u = ppl[i], v = ppl[i+1];
if(is_ancestor(u, v) || is_ancestor(v, u)){res++;continue;}
int up_u = lca(u, v), up_v = lca(v, u);
if(up_u > up_v) break;
res++;
}
cout << res << endl;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
input:
8 5 1 2 4 8 4 6 1 4 2 5 4 7 2 3 5 2 6 4 8
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
4 4 1 2 1 3 1 4 3 2 3 4
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
2 2 1 2 2 2
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 143ms
memory: 34116kb
input:
200000 200000 161672 172858 146306 146322 61159 61510 140802 145171 194221 195447 73888 80278 77016 77115 1382 1417 186221 195091 78442 78451 171750 172141 147707 151432 182664 182798 143183 147414 156646 162546 6630 6706 18452 18519 99764 99811 153419 153707 125659 129068 179317 185954 13947 14278 ...
output:
74
result:
wrong answer 1st lines differ - expected: '3563', found: '74'