QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603258 | #8716. 树 | frs | TL | 3ms | 12864kb | C++14 | 3.0kb | 2024-10-01 15:32:47 | 2024-10-01 15:32:48 |
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) {
s.insert(i);
}
int QO=0;
for(auto i=s.begin();QO<=m;QO++){
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++;
}
while (q--){
cin >> x >> y;
if (m == 1 || m == 2){
cout << m << "\n";
continue;
}
b[x]=y;
auto i=s.begin();
while(*i<x) i++;
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<10;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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12864kb
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: 3ms
memory: 12692kb
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
Time Limit Exceeded
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...