QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603277 | #8716. 树 | frs | WA | 549ms | 17132kb | C++14 | 2.9kb | 2024-10-01 15:39:05 | 2024-10-01 15:39:06 |
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;
}
int dis(int x, int y){
int z = lca(x, y);
return dep[y]+dep[x]-2*dep[z];
}
bool check(int x, int y, int on){
return dis(x, on)+ dis(y, on) == dis(x, y);
}
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 j = 1; j <= 20; ++j) {
for (int i = 1; i <= n; ++i) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i = 1; i <= m; ++i) {
if (s.size() <= 1) s.insert(i);
else{
auto j = s.rbegin();
j++;
if (check(b[*j], b[i], b[*s.rbegin()])) s.erase(*s.rbegin());
s.insert(i);
}
}
while (q--){
cin >> x >> y;
if (m == 1 || m == 2){
cout << m << "\n";
continue;
}
b[x]=y;
auto i=s.lower_bound(x);
i--;
if(i!=s.begin()) i--;
if(i!=s.begin()) i--;
if(i!=s.begin()) i--;
s.insert(x);
if(x!=1) s.insert(x-1);
if(x!=m) s.insert(x+1);
for(int PO=0;PO < 7;PO++){
if(i==s.end()) break;
auto j=i;
j++;
if(j==s.end()) break;
auto k=j;
k++;
if(k==s.end()) break;
if(check(b[*i], b[*k], b[*j])) s.erase(*j);
else i++;
}
printf("%d\n",(int)s.size());
}
}
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: 12720kb
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: 0
Accepted
time: 2ms
memory: 12508kb
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:
174 175 175 175 175 175 175 175 175 175 176 176 176 176 176 176 175 175 175 175 174 173 173 173 173 173 173 174 174 174 174 173 173 174 174 174 174 174 174 174 174 174 173 173 173 174 173 173 174 173 174 174 174 174 174 174 174 174 174 174 174 175 174 174 174 174 174 175 175 177 177 177 177 177 176 ...
result:
ok 200 numbers
Test #3:
score: -100
Wrong Answer
time: 549ms
memory: 17132kb
input:
1000 200000 200000 142 266 266 877 877 673 673 473 923 473 923 55 55 288 679 288 85 679 85 460 296 460 793 296 262 793 40 262 40 680 647 680 999 647 56 999 550 56 550 774 774 939 939 423 423 168 168 554 554 93 329 93 329 474 221 474 890 221 890 304 752 304 345 752 345 269 290 269 290 781 781 264 859...
output:
133598 133598 133598 133598 133598 133598 133596 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133596 133596 133596 133596 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133598 133596 133596 133596 133596 133596...
result:
wrong answer 140343rd numbers differ - expected: '133344', found: '133345'