QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236134#6406. Stage ClearPaxton#WA 2ms5740kbC++235.9kb2023-11-03 16:55:002023-11-03 16:55:00

Judging History

This is the latest submission verdict.

  • [2024-08-15 21:05:17]
  • hack成功,自动添加数据
  • (/hack/778)
  • [2023-11-03 16:55:00]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5740kb
  • [2023-11-03 16:55:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
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)
{
    for (int i = 0; i < edge[now].size(); ++i)
    {
        int id = edge[now][i].id;
        if (id == fa)
            continue;
        dep[id] = dep[now] + 1;
        // cout << id << " " << dep[id] << endl;
        edge[now][i].dep = dep[id];
        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 poi = tmp[1].size() - 1;                 // poi表示chang的指针
        for (int i = tmp[2].size() - 1; i >= 0; i--) // i表示duan的指针
        {
            while (poi >= 0 && tmp[1][poi].first <= tmp[2][i].first) // 若长指针深度小于短指针深度
            {
                if (retu.sign != 0)
                    return node{-1, -1, -1};
                retu = node{1, tmp[1][poi].first, tmp[1][poi].second};
                poi--;
            }
            if (poi >= 0 && tmp[1][poi].first > tmp[2][i].first) // 长指针深度大于短指针深度
            {
                ans.push_back({tmp[1][poi].second, tmp[2][i].second}); // 匹配
                poi--;                                                 // 移位
            }
            else
                return node{-1, -1, -1};
        }
        while (poi >= 0) // 如果duan匹配完了,但是chang还有剩余
        {
            if (retu.sign != 0)
                return node{-1, -1, -1};
            retu = node{1, tmp[1][poi].first, tmp[1][poi].second};
            poi--; // 剩一个且之前没剩
        }
    }
    else if (tmp[1].size() < tmp[2].size()) // 同理
    {
        int poi = 0;
        for (int i = 0; i < tmp[1].size(); i++)
        {
            while (poi < tmp[2].size() && tmp[1][i].first <= tmp[2][poi].first)
            {
                if (retu.sign != 0)
                    return (node){-1, -1, -1};
                retu = (node){2, tmp[2][poi].first, tmp[2][poi].second}, poi++;
            }
            if (poi < tmp[2].size() && tmp[1][i].first > tmp[2][poi].first)
            {
                ans.push_back({tmp[1][i].second, tmp[2][poi].second});
                poi++;
            }
            else
                return node{-1, -1, -1};
        }
        while (poi < tmp[2].size())
        {
            if (retu.sign != 0)
                return node{-1, -1, -1};
            retu = node{2, tmp[2][poi].first, tmp[2][poi].second};
            poi++;
        }
    }
    return retu;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int a, p;
        string t;
        int tt;
        cin >> a >> p >> t;
        if (t == "-")
            tt = 0;
        else if (t == "Chang")
            tt = 1;
        else if (t == "Duan")
            tt = 2;
        else if (t == "Tong")
            tt = 3;
        edge[p].push_back(node{tt, 0, a});
        sign[a] = tt;
    }
    dep[1] = 1;
    dfs(1, 0);
    node finish = dfs1(1, 0);
    if (finish.sign == 0)
    {
        cout << "YES" << endl;
        for (auto [u, v] : ans)
        {
            cout << u << " " << v << endl;
        }
    }
    else
        cout << "NO" << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 5740kb

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