QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#593177#7738. Equivalent RewritingflsRE 2ms10748kbC++144.9kb2024-09-27 12:20:062024-09-27 12:20:08

Judging History

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

  • [2024-09-27 12:20:08]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:10748kb
  • [2024-09-27 12:20:06]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <stack>

/*template <class T, size_t size = std::tuple_size<T>::value> std::string to_debug(T, std::string s = "") requires(not std::ranges::range<T>);
std::string to_debug(auto x) requires requires(std::ostream& os) { os << x; } { return static_cast<std::ostringstream>(std::ostringstream() << x).str(); }
std::string to_debug(std::ranges::range auto x, std::string s = "") requires(not std::is_same_v<decltype(x), std::string>) {
  for (auto xi : x) { s += ", " + to_debug(xi); }
  return "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size> std::string to_debug(T x, std::string s) requires(not std::ranges::range<T>) {
  [&]<size_t... I>(std::index_sequence<I...>) { ((s += ", " + to_debug(get<I>(x))), ...); }(std::make_index_sequence<size>());
  return "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << __LINE__ << ": (" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << "\n"
#else
#define debug(x...)
#endif*/

using i64 = long long;

const int mxn = 1e5+5;

std::priority_queue <int> que;

std::set <int> edge[mxn];

std::vector <int> ans, u[mxn];

int r[mxn], num[mxn];

int n, m;

bool suc, tag[mxn];

void init(){
    suc = false;
    ans.clear();
    //std::que.clear();
    //que.clear();
    while(que.size()){
        que.pop();
    }
    for(int i = 0 ; i <= std::max(m,n) ; i++){
        //r[i] = 0;
        num[i] = 0;
        //tag[i] = false;
        //edge[i].clear();
    }
    for(int i = 0 ; i <= std::max(n,m); i++){
        r[i] = 0;
        tag[i] = false;
        edge[i].clear();
        u[i].clear();
    }
}

bool check(){
    for(int i = 0 ; i < (int)ans.size() ; i++)
        if(i + 1 != ans[i])
            return false;
    return true;
}

void solve()
{
#define tests
    //std::set <int> edge[mxn];
    int pt;
    std::cin >> n >> m;
    init();
    for(int pi, i = 1 ; i <= n ; i++){
        std::cin >> pi;
        for(int pos, j = 1 ; j <= pi ; j++){
            std::cin >> pos;
            u[pos].push_back(i);
            num[pos] = i;
        }
        //std::cerr << i << ":" << pi << std::endl;
    }
    if (n == 1) {
        std::cout << "No\n";
        return;
    }
    for(int i = 1 ; i <= m ; i++)
        if(!tag[num[i]])
            tag[num[i]] = true;
    tag[0]=false;
    for(int i=1;i<=n;i++){
        for(int j=0;j<u[i].size()-1;j++){
            //std::cerr << u[i][j] << "-->" << num[i] << "\n";
            edge[u[i][j]].insert(num[i]);
            //std::cerr << u[i][j] << "-->" << num[i] << "\n";
            r[num[i]]++;
            //std::cerr << u[i][j] << "-->" << num[i] << "\n";
        }
        //std::cerr << i << std::endl;
    }
    //std::cerr << "suc" << std::endl;
    for(int i = 1 ; i <= n ; i++){
        if(!r[i]){
            que.push(i);
        }
    }
    if(que.size() > 1){
        suc = true;
    }

    while(!que.empty()){
        pt = que.top();
        if(que.size() > 1)
            suc = true;
        que.pop();
        ans.push_back(pt);
        for(auto x : edge[pt]){
            //debug(pt, x, r[x]);
            r[x]--;
            if(!r[x])
                que.push(x);
        }
        if(que.size() > 1)
            suc = true;
    }

    if(!suc||check()){
        suc = false;
        int cnt = 0, cnt_pos[2];
        for(int i = 0 ; i < (int)ans.size() ; i++){
            if(!tag[ans[i]]){
                cnt_pos[cnt] = i;
                cnt++;
            }
            if(cnt == 2){
                if(ans[cnt_pos[0]] < ans[cnt_pos[1]])
                    std::swap(ans[cnt_pos[0]], ans[cnt_pos[1]]);
                suc = true;
                break;
            }
        }
        if(!suc){
            if(cnt==1&&ans[cnt_pos[0]]!=1){
                    ans.insert(ans.begin(), ans[cnt_pos[0]]);
                    ans.erase(ans.begin()+cnt_pos[0]+1);
                    suc=true;
            }
        }
    }
    


    if(suc){
        std::cout << "Yes\n";
        for(int i = 0 ; i < ans.size() - 1 ; i++)
            std::cout << ans[i] << " ";
        std::cout << ans[ans.size() - 1];
        std::cout << "\n";
    }else{
        std::cout << "No\n";
    }
}
 
signed main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int _{1};
#ifdef tests
    std::cin >> _;
#endif
    while(_--) solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10748kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
3 1 2
No
No

result:

ok OK. (3 test cases)

Test #2:

score: -100
Runtime Error

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:


result: