QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602675 | #8716. 树 | frs# | WA | 0ms | 12768kb | C++14 | 3.0kb | 2024-10-01 11:54:08 | 2024-10-01 11:54:09 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include <valarray>
#include <cmath>
#include <numeric>
#include <random>
#include <set>
using namespace std;
#define ll long long
//#define int ll
const int maxN = 2e5+10, mod = 998244353, inf = 1e9+10;
int n, m, q, b[maxN], fa[maxN][30], dep[maxN];
ll power(ll x, ll y){
ll an = 1;
while(y){
if (y&1) an = an*x % mod;
y >>= 1;
x = x*x %mod;
}
return an;
}
ll inv(ll x){
return power(x, mod-2);
}
vector<int> v[maxN];
set<int> s;
void dfs(int x, int last, int d){
dep[x] = d;
fa[x][0] = last;
for (auto i:v[x]){
if (i == last) continue;
dfs(i, x, d+1);
}
}
int lca(int x, int y){
if (dep[x] > dep[y]) swap(x, y);
int z = dep[y]-dep[x], c = 0;
while (z){
if (z & 1) y = fa[y][c];
z >>= 1;
c++;
}
if (x == y) return x;
for (int i = 20; i >= 0; --i) {
if (fa[x][i] == fa[y][i]) continue;
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
bool is_fa(int son, int f){
if (son == f) return false;
return lca(son, f) == f;
}
bool check(int x, int y, int on){
if (dep[x] > dep[y]) swap(x, y);
if (dep[on] < dep[x]) return lca(x, on) == on && lca(y, on) == on;
if (dep[on] > dep[y]) return false;
return lca(x, on) == x && lca(y, on) == on;
}
void solve(){
cin >> n >> m >> q;
int x, y;
for (int i = 1; i < n; ++i) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= m; ++i) cin >> b[i];
dfs(1, 0, 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 20; ++j) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i = 1; i <= m; ++i) {
if (!s.empty() && b[i] == *s.rbegin()) continue;
if (s.size() <= 1) s.insert(i);
else{
auto j = s.rbegin();
j++;
if (check(b[*j], b[i], b[*s.rbegin()])) continue;
else s.erase(*s.rbegin()), s.insert(i);
}
}
while (q--){
cin >> x >> y;
if (m == 1){
cout << 1 << "\n";
continue;
}
b[x] = y;
if (x == 1){
auto i = s.lower_bound(x);
if (!check(b[*i], b[x], b[x+1])) s.insert(x+1);
cout << s.size()+1 << "\n";
}else if (x == n){
auto i = s.rbegin();
i++;
if (!check(b[*i], b[x], b[x-1])) s.insert(x-1);
cout << s.size()+1 << "\n";
}else{
if (!check(b[x-1], b[x+1], b[x])){
if (check(b[x-1], b[x], b[x+1])) s.insert(x+1), s.insert(x);
else s.insert(x), s.insert(x-1);
}
cout << s.size()+1 << "\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
int t = 1;
while (t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 12768kb
input:
5 5 3 2 1 3 2 1 4 5 1 1 5 4 2 3 1 3 5 3 3 3
output:
4 4 5
result:
ok 3 number(s): "4 4 5"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 10796kb
input:
30 200 200 10 24 10 13 10 26 13 29 27 26 17 24 27 21 17 15 13 5 13 30 27 3 18 21 9 21 2 24 10 4 11 5 2 8 10 23 1 18 21 25 4 20 12 23 22 27 28 27 18 7 13 6 14 30 10 19 16 21 14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...
output:
5 7 9 10 10 12 14 16 18 20 22 24 26 28 30 32 34 36 37 38 40 42 44 46 48 48 50 51 53 55 57 57 57 57 59 61 63 65 67 69 69 71 72 73 75 76 78 80 81 81 81 82 84 84 86 87 87 87 89 91 91 93 93 93 93 94 94 95 96 98 99 99 101 101 101 103 103 103 104 106 108 108 110 112 113 115 115 115 115 115 117 117 119 121...
result:
wrong answer 1st numbers differ - expected: '174', found: '5'