QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#603274	#8716. 树	UESTC_PenaltyAutomaton	WA	1ms	10264kb	C++17	3.5kb	2024-10-01 15:37:41	2024-10-01 15:37:42

Judging History

你现在查看的是最新测评结果

[2024-10-01 15:37:42]
评测

测评结果：WA
用时：1ms
内存：10264kb

查看

[2024-10-01 15:37:41]
提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N = 2e5 + 5;

int n, m, qr, p, g, b[N], ans;
int fa[N][22], deg[N];
bool f[N];

struct Edge{
	int to, nxt;
}edge[N * 2];
int head[N], tot;
void addedge(int uu, int vv){
	edge[tot].to = vv;
	edge[tot].nxt = head[uu];
	head[uu] = tot++;
}
void init(){
	tot = 0;
	memset(head, -1, sizeof(head));
}

void bfs(int root){
	queue<int> que;
	deg[root] = 0;
	fa[root][0] = root;
	que.push(root);
	while(!que.empty()){
		int tmp = que.front();
		que.pop();
		for(int i = 1; i <= 20; i++){
			fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
		}
		for(int i = head[tmp]; i != -1; i = edge[i].nxt){
			int v = edge[i].to;
			if(v == fa[tmp][0]) continue;
			deg[v] = deg[tmp] + 1;
			fa[v][0] = tmp;
			que.push(v);
		}
	}
}

int lca(int u, int v){
	if(deg[u] > deg[v]) swap(u, v);
	int hu = deg[u], hv = deg[v];
	int tu = u, tv = v;
	for(int det = hv - hu, i = 0; det; det >>= 1, i++){
		if(det & 1) tv = fa[tv][i];
	}
	if(tu == tv) return tu;
	for(int i = 20; i>= 0; i--){
		if(fa[tu][i] == fa[tv][i]) continue;
		tu = fa[tu][i];
		tv = fa[tv][i];
	}
	return fa[tu][0];
}

void check(int i){
    int l = 0, r = 0, z = 0, ret;
    ret = lca(b[i - 1], b[i + 1]);
    if(ret == b[i - 1]) l++;
    else if(ret == b[i + 1]) r++;
    ret = lca(b[i - 1], b[i]);
    if(ret == b[i - 1]) l++;
    else if(ret == b[i]) z++;
    ret = lca(b[i], b[i + 1]);
    if(ret == b[i]) z++;
    else if(ret == b[i + 1]) r++;
    
    if(f[i] == 1){
        if(l == 2 && z == 1) f[i] = 0;
        else if(r == 2 && z == 1) f[i] = 0;
        else if(l == 0 && r == 0 && (z == 1 || z == 3)){
            f[i] = 0;
        }
        if(b[i] == b[i + 1]) f[i] = 0;
        if(f[i] == 0) ans--;
    }
    else{
        if(l == 2 && z == 1) f[i] = 0;
        else if(r == 2 && z == 1) f[i] = 0;
        else if(l == 0 && r == 0 && (z == 1 || z == 3)){
            f[i] = 0;
        }
        else if(b[i] == b[i + 1]) f[i] = 0;
        else{
            f[i] = 1;
            ans++;
        }
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &qr);
    init();
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    for(int i = 1; i <= m; i++){
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 20; ++j) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    bfs(1);
    f[1] = 1;
    f[m] = 1;
    for(int i = 2; i < m; i++){
        int l = 0, r = 0, z = 0, ret;
        ret = lca(b[i - 1], b[i + 1]);
        if(ret == b[i - 1]) l++;
        else if(ret == b[i + 1]) r++;
        ret = lca(b[i - 1], b[i]);
        if(ret == b[i - 1]) l++;
        else if(ret == b[i]) z++;
        ret = lca(b[i], b[i + 1]);
        if(ret == b[i]) z++;
        else if(ret == b[i + 1]) r++;
        
        f[i] = 1;
        if(l == 2 && z == 1) f[i] = 0;
        else if(r == 2 && z == 1) f[i] = 0;
        else if(l == 0 && r == 0 && (z == 1 || z == 3)){
            f[i] = 0;
    	}
    }
    ans = 0;
    for(int i = 1; i <= m; i++){
        if(f[i]) ans++;
    }
    while(qr--){
        scanf("%d%d", &p, &g);
        b[p] = g;
        if(p > 1 && p < m) check(p);
        if(p - 1 > 1 && p - 1 < m) check(p - 1);
        if(p + 1 > 1 && p + 1 < m) check(p + 1);
        printf("%d\n", ans);
    }
    return 0;
}


/*

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

*/

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 4576kb

input:

output:

4
4
5

result:

ok 3 number(s): "4 4 5"

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 10264kb

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:

result:

wrong answer 1st numbers differ - expected: '174', found: '180'