#1RE #2#4WA 求调(怀疑评测机)
  • 板块P1347 排序
  • 楼主Shy_Vector
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/21 21:28
  • 上次更新2024/9/21 21:39:50
查看原帖
#1RE #2#4WA 求调(怀疑评测机)
369915
Shy_Vector楼主2024/9/21 21:28

\n全RE(本地输出正确)

\r\n#1RE,#2#4WA(本地无法运行)

#include <iostream>
#include <vector>
// #include <queue>
#include <set>
using namespace std;

vector<int> edge[100];
// queue<int> que;
set<int> vis;
string ans;
int indeg[100];
size_t n, m;

bool is_err(set<int> cur_vis, int cur_indeg[100]) {
    if (cur_vis.empty()) {
        return 0;
    }
    for (auto it = cur_vis.begin(); it != cur_vis.end(); it++) {
        int u = *it;
        if (!cur_indeg[u]) {
            ans += 'A' + u;
            for (int v : edge[u]) {
                if (cur_vis.count(v)) cur_indeg[v]--;
            }
            cur_vis.erase(it);
            int nex_indeg[100];
            for (int i = 0; i < 100; i++) {
                nex_indeg[i] = cur_indeg[i];
            }
            return is_err(cur_vis, nex_indeg);
        }
    }
    return 1;
}

int main() {
    // freopen("P1347_1.in", "r", stdin);
    // freopen("P1347_1_test.out", "w", stdout);
    cin >> n >> m;
    for (size_t i = 1; i <= m; i++) {
        getchar(); //吞\r
        getchar(); //吞\n
        char uc, vc;
        scanf("%c<%c", &uc, &vc);
        int u = uc - 'A', v = vc - 'A';
        // printf("%d %d\n", u, v);
        vis.insert(u), vis.insert(v);
        edge[u].push_back(v);
        indeg[v]++;
        int indeg_tmp[100];
        for (int j = 0; j < 100; j++) {
            indeg_tmp[j] = indeg[j];
        }
        if (is_err(vis, indeg_tmp)) {
            printf("Inconsistency found after %zd relations.", i);
            // fclose(stdin);
            // fclose(stdout);
            return 0;
        } else if (vis.size() >= n) {
            printf("Sorted sequence determined after %zd relations: %s.", i, ans.c_str());
            // fclose(stdin);
            // fclose(stdout);
            return 0;
        }
        ans.clear();
    }
    printf("Sorted sequence cannot be determined.");
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}
2024/9/21 21:28
加载中...