QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387090 | #8029. Traveling Merchant | 15owzLy1 | Compile Error | / | / | C++20 | 3.6kb | 2024-04-12 01:47:35 | 2024-04-12 01:47:36 |
Judging History
你现在查看的是最新测评结果
- [2024-08-07 20:25:21]
- hack成功,自动添加数据
- (/hack/771)
- [2024-04-12 01:47:36]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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 | |