QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#784045#7738. Equivalent RewritingadivseWA 1ms3564kbC++203.4kb2024-11-26 12:56:042024-11-26 12:56:04

Judging History

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

  • [2024-11-26 12:56:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3564kb
  • [2024-11-26 12:56:04]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
template<typename T>
void cc(const vector<T>& tem) { for (const auto& x : tem) cout << x << ' '; cout << endl; }
template<typename T>
void cc(const T& a) { cout << a << endl; }
template<typename T1, typename T2>
void cc(const T1& a, const T2& b) { cout << a << ' ' << b << endl; }
template<typename T1, typename T2, typename T3>
void cc(const T1& a, const T2& b, const T3& c) { cout << a << ' ' << b << ' ' << c << endl; }
void cc(const string& s) { cout << s << endl; }
void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\cppvscode\\CODE\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\cppvscode\\CODE\\out.txt", "w", stdout);
#endif
}
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) { if (a < b) return b; return a; }
inline double max(double a, double b) { if (a < b) return b; return a; }
inline int min(int a, int b) { if (a < b) return a; return b; }
inline double min(double a, double b) { if (a < b) return a; return b; }
void cmax(int& a, const int& b) { if (b > a) a = b; }
void cmin(int& a, const int& b) { if (b < a) a = b; }
void cmin(double& a, const double& b) { if (b < a) a = b; }
void cmax(double& a, const double& b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int>>;
using que_int = std::queue<int>;


//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;
vec_int A[N];
vec_int val[N];
int in[N];
vec_int ans;
//--------------------------------------------------------------------------------
//struct or namespace:

//--------------------------------------------------------------------------------

void dfs() {

    que_int F;
    rep(i, 1, n) {
        if (in[i] != 0) continue;
        F.push(i);
        // cc(i);
    }
    while (!F.empty()) {
        auto x = F.front(); F.pop();
        ans.push_back(x);
        for (auto y : A[x]) {
            in[y]--;
            if (in[y] == 0) F.push(y);
        }
    }
    if (ans.size() == n) {
        cc("Yes");
        cc(ans);
    }
    else {
        cc("No");
    }
}

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> m;

        ans.clear();
        rep(i, 1, n) { A[i].clear(); }
        rep(i, 1, m) {
            in[i] = 0;
            val[i].clear();
        }

        rep(i, 1, n) {
            int a; cin >> a;
            rep(j, 1, a) {
                int b; cin >> b;
                val[b].push_back(i);
            }
        }
        rep(i, 1, m) {
            if (val[i].empty()) continue;
            int len = val[i].size();
            rep(j, 0, len - 1 - 1) {
                A[val[i][j]].push_back(val[i][len - 1]);
                in[val[i][len - 1]]++;
            }
        }
        dfs();

    }
    return 0;
}
/*


*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3564kb

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
1 3 2 
Yes
1 2 
Yes
1 

result:

wrong answer two transactions are same. (test case 2)