QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578725#9284. Christmas Children Circlesea_birdWA 3ms27844kbC++201.9kb2024-09-20 21:00:352024-09-20 21:00:36

Judging History

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

  • [2024-09-20 21:00:36]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:27844kb
  • [2024-09-20 21:00:35]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
const int maxn = 5e5 + 100;
std::map<int, int>mp[maxn];
std::vector<int>arr[maxn];
int give[maxn];
void solve() {
    int n;
    std::cin >> n;
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        int siz;
        std::cin >> siz;
        for (int j = 1; j <= siz; j++) {
            int x;
            std::cin >> x;
            mp[i][x]++;
            if (mp[i][x] == 2) {
                arr[i].push_back(x);
            }
            if (arr[i].size() > 1 or mp[i][x] > 2)
                flag = false;
        }
    }
    if (!flag) {
        std::cout << "-1\n";
        return;
    }
    std::queue<pii>que;
    for (int i = 1; i <= n; i++) {
        for (auto x : arr[i]) {
            if (mp[i][x] > 1) {
                que.push({i, x});
                break;
            }
        }
    }
    while (!que.empty()) {
        auto [u, v] = que.front();
        que.pop();
        if (give[u]) {
            std::cout << "-1\n";
            return;
        }
        give[u] = v;
        int nxt = u % n + 1;
        if (mp[nxt][v] > 0) {
            que.push({nxt, v});
        }
    }
    std::vector<pii>qp;
    for (int i = 1; i <= n; i++) {
        if (give[i])
            continue;
        qp.push_back({mp[i].size(), i});
    }
    std::sort(qp.begin(), qp.end());
    for (auto [siz, u] : qp) {
        int nxt = u % n + 1;
        for (auto [x, v] : mp[u]) {
            if (mp[nxt][x] <= 0 and v > 0) {
                give[u] = x;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        std::cout << give[i] << " \n"[i == n];
    }
}
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 27844kb

input:

3
2 1 4
2 4 3
2 3 1

output:

1 4 3

result:

ok Participant's answer is valid

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 27048kb

input:

4
1 2
1 3
1 5
1 2

output:

2 3 5 0

result:

wrong answer x[3]=0 does not belong to a[3]