社区讨论

TLE/RE 求调

P3884[JLOI2009] 二叉树问题参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m63eiv3j
此快照首次捕获于
2025/01/19 17:14
去年
此快照最后确认于
2025/11/04 11:17
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int l[110], r[110], f[110], lv[110], n;
queue<int> p, q, s;
void clear(){
    while(!p.empty()) p.pop();
    while(!q.empty()) q.pop();
    while(!s.empty()) s.pop();
}
int bfs1(){
    clear();
    p.push(1); q.push(1); lv[1]++; int ans = 0; 
    while(!p.empty()){
        ans = max(ans, q.front());
        if(l[p.front()]){
            p.push(l[p.front()]), q.push(q.front() + 1);
            lv[q.front() + 1]++;
        }
        if(r[p.front()]){
            p.push(r[p.front()]), q.push(q.front() + 1);
            lv[q.front() + 1]++;
        }
        p.pop(), q.pop();
    }
    cout << ans << endl;
    ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, lv[i]);
    cout << ans << endl;
}
int bfs2(int x, int y){
    clear();
    p.push(x); q.push(0); s.push(0);
    while(!p.empty()){
        if(p.front() == y) return q.front();
        if(s.front() != f[p.front()] && f[p.front()]){
            p.push(f[p.front()]);
            q.push(q.front() + 2); 
            s.push(p.front());
        }
        if(s.front() != l[p.front()] && l[p.front()]){
            p.push(l[p.front()]);
            q.push(q.front() + 1); 
            s.push(p.front());
        }
        if(s.front() != r[p.front()] && r[p.front()]){
            p.push(r[p.front()]);
            q.push(q.front() + 1); 
            s.push(p.front());
        }
        p.pop(); q.pop(), s.pop();
    }
}
int main(){
    int u, v;
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> u >> v;
        if(l[u]) r[u] = v;
        else l[u] = v;
        f[v] = u;
    }
    cin >> u >> v;
    bfs1();
    cout << bfs2(u, v);
}
开 O2 会全 TLE,不开会 RE(反馈是 illegal instruction,查了一下,“执行了一条不支持的 CPU 指令”,懵了)
本地/IDE 能过样例,大家帮我一下,谢谢
提交/IDE 选项都是 C++14

回复

0 条回复,欢迎继续交流。

正在加载回复...