QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#387090#8029. Traveling Merchant15owzLy1Compile Error//C++203.6kb2024-04-12 01:47:352024-04-12 01:47:36

Judging History

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

  • [2024-08-07 20:25:21]
  • hack成功,自动添加数据
  • (/hack/771)
  • [2024-04-12 01:47:36]
  • 评测
  • [2024-04-12 01:47:35]
  • 提交

answer

#include <bits/stdc++.h>
​
const int N = 2e5 + 5;
​
struct edge {
    int next, to;
} e[N << 1];
int ecnt, ehead[N];
​
int dfn_tot, bel_tot;
int dfn[N], low[N], bel[N], dep[N];
bool vis[N], bridge[N];
​
int fa[N][20];
int n, m;
​
inline void AddEdge(const int u, const int v) {
    e[++ecnt] = {ehead[u], v}, ehead[u] = ecnt;
    e[++ecnt] = {ehead[v], u}, ehead[v] = ecnt;
}
​
void init() {
    ecnt = 1;
    dfn_tot = bel_tot = 0;
    memset(ehead, 0, sizeof(int) * (n + 1));
    memset(dfn, 0, sizeof(int) * (n + 1));
    memset(bel, 0, sizeof(int) * (n + 1));
    memset(bridge, false, sizeof(bool) * (m + 1));
}
​
void dfs(const int u, const int pre = -1) {
    for (int i = 1; i < 20; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    dfn[u] = low[u] = ++dfn_tot;
    for (int i = ehead[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (dfn[v] == 0) {
            fa[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v, i);
            low[u] = std::min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                bridge[i / 2] = true;
            }
        } else if (i != (pre^1)) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }
}
​
void Shrink(const int u) {
    bel[u] = bel_tot;
    for (int i = ehead[u]; i; i = e[i].next) {
        auto v = e[i].to;
        if (bel[v] == 0 && !bridge[i / 2]) {
            Shrink(v);
        }
    }
}
​
void Tarjan() {
    dep[1] = 1;
    memset(fa[1], 0, sizeof(fa[1]));
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        if (bel[i] == 0 && dfn[i] != 0) {
            ++bel_tot;
            Shrink(i);
        }
    }
}
​
int GetLca(int u, int v) {
    if (dep[u] > dep[v]) {
        std::swap(u, v);
    }
    for (int i = 19; i >= 0; --i)
        if (dep[fa[v][i]] >= dep[u])
            v = fa[v][i];
    if (u == v) {
        return u;
    }
    for (int i = 19; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
​
int main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    int ttt;
    std::cin >> ttt;
    while (ttt--) {
        std::vector<std::pair<int,int>> diff;
        std::string cl;
        std::cin >> n >> m;
        std::cin >> cl;
        cl = "*" + cl;
        init();
        std::set<std::pair<int,int>> mp;
        for (int i = 0, u, v; i < m; ++i) {
            std::cin >> u >> v;
            ++u, ++v;
            if (u > v) {
                std::swap(u, v);
            }
            assert(mp.count({u, v}) == 0);
            mp.insert({u, v});
            if (cl[u] == cl[v]) {
                diff.emplace_back(u, v);
                //for (auto &[x, y]: diff) {
                //    std::cout << x << ' ' << y << std::endl;
                //}
            } else {
                AddEdge(u, v);
            }
        }
        Tarjan();
        bool flag = false;
        for (auto &[u, v]: diff) {
            if (dfn[u] == 0 || dfn[v] == 0) {
                continue;
            }
            int w = GetLca(u, v);
            // printf("%d %d %d  %d %d %d\n", w, u, v, fa[w][0], bel[u], bel[v]);
            if (w == u || w == v) {
                flag = true;
                break;
            }
            if (bel[fa[w][0]] == bel[u] || bel[fa[w][0]] == bel[v]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            std::cout << "yes\n";
        } else {
            std::cout << "no\n";
        }
    }
    return 0;
}

详细

answer.code:2:1: error: ‘​’ does not name a type
    2 | ​
      |  
answer.code:4:1: error: ‘​’ does not name a type
    4 | ​
      |  
answer.code:7:3: error: ‘e’ does not name a type
    7 | } e[N << 1];
      |   ^
answer.code:8:17: error: ‘N’ was not declared in this scope
    8 | int ecnt, ehead[N];
      |                 ^
answer.code:9:1: error: ‘​’ does not name a type
    9 | ​
      |  
answer.code:11:9: error: ‘N’ was not declared in this scope
   11 | int dfn[N], low[N], bel[N], dep[N];
      |         ^
answer.code:11:17: error: ‘N’ was not declared in this scope
   11 | int dfn[N], low[N], bel[N], dep[N];
      |                 ^
answer.code:11:25: error: ‘N’ was not declared in this scope
   11 | int dfn[N], low[N], bel[N], dep[N];
      |                         ^
answer.code:11:33: error: ‘N’ was not declared in this scope
   11 | int dfn[N], low[N], bel[N], dep[N];
      |                                 ^
answer.code:12:10: error: ‘N’ was not declared in this scope
   12 | bool vis[N], bridge[N];
      |          ^
answer.code:12:21: error: ‘N’ was not declared in this scope
   12 | bool vis[N], bridge[N];
      |                     ^
answer.code:13:1: error: ‘​’ does not name a type
   13 | ​
      |  
answer.code:16:1: error: ‘​’ does not name a type
   16 | ​
      |  
answer.code:21:1: error: ‘​’ does not name a type
   21 | ​
      |  
answer.code:30:1: error: ‘​’ does not name a type
   30 | ​
      |  
answer.code:51:1: error: ‘​’ does not name a type
   51 | ​
      |  
answer.code:61:1: error: ‘​’ does not name a type
   61 | ​
      |  
answer.code:73:1: error: ‘​’ does not name a type
   73 | ​
      |  
answer.code:89:1: error: ‘​’ does not name a type
   89 | ​
      |