QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#236168 | #6406. Stage Clear | Paxton# | WA | 0ms | 5824kb | C++23 | 5.9kb | 2023-11-03 17:30:08 | 2023-11-03 17:30:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
struct node
{
int sign, dep, id;
};
vector<node> edge[maxn];
int dep[maxn];
int sign[maxn];
vector<pair<int, int>> ans;
void dfs(int now, int fa)
{
dep[now] = dep[fa] + 1;
for (int i = 0; i < edge[now].size(); ++i)
{
int id = edge[now][i].id;
if (id == fa)
continue;
dfs(id, now);
}
}
node dfs1(int now, int fa)
{
vector<pair<int, int>> tmp[4]; // 待处理序列 tmp[sign] = {<dep,id>}
node retu = node{0, 0, 0}; // 当层返回值,id=-1表示无解,0表示没有点
for (node a : edge[now])
{
if (a.id == fa)
continue;
node rec = dfs1(a.id, now); // return仅能返回一个点的值
if (rec.sign == -1) // 返回-1说明无解
return node{-1, -1, -1};
else if (rec.sign > 0) // 返回1,2,3说明有返回点
tmp[rec.sign].push_back({rec.dep, rec.id}); // 加入待处理序列
} // 所有儿子节点情况已经添加到tmp中
if (sign[now] != 0) // 自己拥有标记,加入匹配序列
tmp[sign[now]].push_back({dep[now], now});
for (int i = 1; i <= 3; ++i)
sort(tmp[i].begin(), tmp[i].end(), greater<pair<int, int>>()); // 按照dep降序排序
if (tmp[3].size())
{
int jishu = 1;
for (int i = 1; i < tmp[3].size(); ++i)
{
if (tmp[3][i].first != tmp[3][i - 1].first) // 存在tong无法匹配
{
if (jishu % 2) // 奇数个tong
{
if (retu.sign != 0) // 存在待返回值
return node{-1, -1, -1}; // 直接返回无解
retu = node{3, tmp[3][i - 1].first, tmp[3][i - 1].second}; // 否则加入返回值
}
for (int j = i - jishu; j < i - 1; j += 2)
ans.push_back({tmp[3][j].second, tmp[3][j + 1].second});
jishu = 1;
}
else
jishu++;
}
for (int i = tmp[3].size() - jishu; i < tmp[3].size() - 1; i += 2) // 处理最后一段tong
ans.push_back({tmp[3][i].second, tmp[3][i + 1].second});
if (jishu % 2) // 奇数个tong,最后一位多余
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{3, tmp[3][tmp[3].size() - 1].first, tmp[3][tmp[3].size() - 1].second};
}
}
if (tmp[1].size() == tmp[2].size()) // chang,duan长度相同
{
for (int i = 0; i < tmp[1].size(); i++)
{
if (tmp[1][i].first <= tmp[2][i].first)
return (node){-1, -1, -1};
ans.push_back({tmp[1][i].second, tmp[2][i].second});
}
}
else if (tmp[1].size() > tmp[2].size())
{
int zz = tmp[1].size() - 1; // zz表示chang的指针
for (int i = tmp[2].size() - 1; i >= 0; i--) // i表示duan的指针
{
while (zz >= 0 && tmp[1][zz].first <= tmp[2][i].first) // 若长指针深度小于短指针深度
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
zz--;
}
if (zz >= 0 && tmp[1][zz].first > tmp[2][i].first) // 长指针深度大于短指针深度
{
ans.push_back({tmp[1][zz].second, tmp[2][i].second}); // 匹配
zz--; // 移位
}
else
return node{-1, -1, -1};
}
while (zz >= 0) // 如果duan匹配完了,但是chang还有剩余
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{1, tmp[1][zz].first, tmp[1][zz].second};
zz--; // 剩一个且之前没剩
}
}
else if (tmp[1].size() < tmp[2].size()) // 同理
{
int zz = 0;
for (int i = 0; i < tmp[1].size(); i++)
{
while (zz < tmp[2].size() && tmp[1][i].first <= tmp[2][zz].first)
{
if (retu.sign != 0)
return (node){-1, -1, -1};
retu = (node){2, tmp[2][zz].first, tmp[2][zz].second}, zz++;
}
if (zz < tmp[2].size() && tmp[1][i].first > tmp[2][zz].first)
{
ans.push_back({tmp[1][i].second, tmp[2][zz].second});
zz++;
}
else
return node{-1, -1, -1};
}
while (zz < tmp[2].size())
{
if (retu.sign != 0)
return node{-1, -1, -1};
retu = node{2, tmp[2][zz].first, tmp[2][zz].second};
zz++;
}
}
return retu;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i < n; ++i)
{
int a, p, si = 0;
string t;
cin >> a >> p >> t;
if (t == "-")
si = 0;
else if (t == "Chang")
si = 1;
else if (t == "Duan")
si = 2;
else if (t == "Tong")
si = 3;
edge[p].push_back(node{si, 0, a});
sign[a] = si;
}
dep[1] = 1;
dfs(1, 0);
node finish = dfs1(1, 0);
if (finish.sign == 0)
{
cout << "YES" << endl;
for (int i = 0; i < ans.size(); i++)
{
if (i != ans.size() - 1)
cout << ans[i].first << " " << ans[i].second << endl;
else
cout << ans[i].first << " " << ans[i].second;
}
}
else
cout << "NO";
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5824kb
input:
4 4 4 2 5 3 2 6 1 2 1 3 2 4 3 4
output:
YES
result:
wrong output format Expected integer, but "YES" found