QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103924#6396. Puzzle: Kusabihos_lyricWA 20ms8868kbC++143.7kb2023-05-07 20:54:442023-05-07 20:54:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-07 20:54:46]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:8868kb
  • [2023-05-07 20:54:44]
  • 提交

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 <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


int N;
vector<int> P;
vector<char> T;

bool solve() {
  vector<int> dep(N, 0);
  for (int u = 1; u < N; ++u) {
    dep[u] = dep[P[u]] + 1;
  }
  vector<vector<int>> dp(N);
  for (int u = 0; u < N; ++u) if (T[u] != '-') {
    dp[u].push_back(u);
  }
  vector<pair<int, int>> ans;
  for (int u = N; --u >= 0; ) {
    vector<pair<int, int>> cs, ds, ts;
    for (const int v : dp[u]) {
      ((T[v] == 'C') ? cs : (T[v] == 'D') ? ds : ts).emplace_back(dep[v], v);
    }
// cerr<<u<<": "<<cs<<" "<<ds<<" "<<ts<<endl;
    sort(cs.begin(), cs.end());
    sort(ds.begin(), ds.end());
    sort(ts.begin(), ts.end());
    const int csLen = cs.size();
    const int dsLen = ds.size();
    const int tsLen = ts.size();
    vector<int> remain;
    if (csLen <= dsLen) {
      // keep smallest in ds
      reverse(cs.begin(), cs.end());
      reverse(ds.begin(), ds.end());
      vector<int> used(dsLen, 0);
      for (int i = 0, j = 0; i < csLen; ++i) {
        for (; j < dsLen && !(cs[i].first > ds[j].first); ++j) {}
        if (j == dsLen) return false;
        used[j] = 1;
        ans.emplace_back(cs[i].second, ds[j].second);
      }
      for (int j = 0; j < dsLen; ++j) if (!used[j]) {
        remain.push_back(ds[j].second);
      }
    } else {
      // keep largest in cs
      vector<int> used(csLen, 0);
      for (int i = 0, j = 0; j < dsLen; ++j) {
        for (; i < csLen && !(cs[i].first > ds[j].first); ++i) {}
        if (i == csLen) return false;
        used[i] = 1;
        ans.emplace_back(cs[i].second, ds[j].second);
      }
      for (int i = 0; i < csLen; ++i) if (!used[i]) {
        remain.push_back(cs[i].second);
      }
    }
    for (int i = 0; i < tsLen; ) {
      if (i + 1 < tsLen && ts[i].first == ts[i + 1].first) {
        ans.emplace_back(ts[i].second, ts[i + 1].second);
        i += 2;
      } else {
        remain.push_back(ts[i].second);
        i += 1;
      }
    }
    if (remain.size() >= 2) {
      return false;
    }
    for (const int v : remain) {
      if (!~P[u]) {
        return false;
      }
      dp[P[u]].push_back(v);
    }
  }
  
  puts("YES");
  for (const auto &e : ans) {
    printf("%d %d\n", e.first + 1, e.second + 1);
  }
  return true;
}

int main() {
  char buf[110];
  
  for (; ~scanf("%d", &N); ) {
    P.assign(N, -1);
    T.assign(N, '-');
    for (int u = 1; u < N; ++u) {
      scanf("%*d%d%s", &P[u], buf);
      --P[u];
      T[u] = buf[0];
    }
    
    const bool res = solve();
    if (!res) {
      puts("NO");
    }
  }
  return 0;
}

詳細信息

Test #1:

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

input:

8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang

output:

YES
8 6
4 5

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang

output:

YES
8 9
10 3
6 2
5 7

result:

ok Correct.

Test #3:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

2
2 1 Tong

output:

NO

result:

ok Correct.

Test #4:

score: -100
Wrong Answer
time: 20ms
memory: 8868kb

input:

100000
2 1 Duan
3 1 Duan
4 3 -
5 4 Duan
6 3 -
7 4 Duan
8 4 -
9 8 -
10 7 Duan
11 9 -
12 7 Duan
13 7 Duan
14 8 Duan
15 13 -
16 10 Duan
17 11 Duan
18 12 -
19 1 Duan
20 5 Duan
21 4 Duan
22 14 Duan
23 16 -
24 22 Duan
25 16 Duan
26 13 -
27 13 -
28 17 -
29 5 Duan
30 22 -
31 23 -
32 9 Duan
33 5 -
34 30 Duan...

output:

NO

result:

wrong answer Jury has answer but participant has not.