QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104771#6396. Puzzle: Kusabigapinho#WA 3ms6372kbC++203.3kb2023-05-11 22:13:202023-05-11 22:13:24

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-11 22:13:24]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6372kb
  • [2023-05-11 22:13:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = __int128_t;

#define int long long

using ii = pair<int, int>;

#define endl '\n'

const int ms = 1e5+50;
const int mod = 998244353;

int typ[ms];
int lvl[ms];
vector<int> g[ms];
int par[ms];

void dfs1(int u) {
  for(int v : g[u]) {
    lvl[v] = lvl[u] + 1;
    dfs1(v);
  }
}

int solve(int u) {
  vector<ii> lfts[4];
  for(int v : g[u]) {
    int x = solve(v);
    if(x) lfts[typ[x]].emplace_back(lvl[x], x);
  }
  if(typ[u]) {
    lfts[typ[u]].emplace_back(lvl[u], u);
  }
  int sob = 0;
  int lst = 0;
  for(int i = 1; i <= 3; i++) sort(lfts[i].begin(), lfts[i].end());
  for(auto [lv, x] : lfts[3]) {
    if(lst == 0) {
      lst = x;
    } else {
      if(lvl[lst] == lv) {
        par[lst] = x;
        par[x] = lst;
        lst = 0;
      } else {
        if(sob != 0 ) {
          cout << "NO" << endl;
          exit(0);
        } else {
          sob = lst;
        }
        lst = x;
      }
    }
  }
  if(lst) {
    if(sob != 0 ) {
      cout << "NO" << endl;
      exit(0);
    } else {
      sob = lst;
    }
  }
  if(lfts[1].size() == lfts[2].size()) {
    for(int i = 0; i < lfts[1].size(); i++) {
      if(lfts[1][i].first > lfts[2][i].first) {
        par[lfts[1][i].second] = lfts[2][i].second;
        par[lfts[2][i].second] = lfts[1][i].second;
      } else {
        cout << "NO" << endl;
        exit(0);
      }
    }
  } else if(abs(((int) lfts[1].size()) - ((int) lfts[2].size())) == 1) {
    if(sob) {
      cout << "NO" << endl;
      exit(0);
    }
    int canSkip = (lfts[1].size() > lfts[2].size()) ? 1 : 2;
    if(canSkip == 2) {
      reverse(lfts[1].begin(), lfts[1].end());
      reverse(lfts[2].begin(), lfts[2].end());
    }
    int i = 0, j = 0;
    while(i < (int) lfts[1].size() && j < (int) lfts[2].size()) {
      if(lfts[1][i].first > lfts[2][j].first) {
        par[lfts[1][i].second] = lfts[2][j].second;
        par[lfts[2][j].second] = lfts[1][i].second;
        i++;
        j++;
      } else {
        if(canSkip == 0) {
          cout << "NO" << endl;
          exit(0);
        } else if(canSkip == 1) {
          sob = lfts[1][i].second;
          i++;
          canSkip = 0;
        } else if(canSkip == 2) {
          sob = lfts[2][j].second;
          j++;
          canSkip = 0;
        }
      }
    }
    if(canSkip == 1) sob = lfts[1].back().second;
    else if(canSkip == 2) sob = lfts[2].back().second;
  } else {
    cout << "NO" << endl;
    exit(0);
  }
  return sob;
}

void solve() {
  int n;
  cin >> n;
  for(int x = 1; x < n; x++) {
    int i, p;
    cin >> i >> p;
    g[p].emplace_back(i);
    string s;
    cin >> s;
    if(s == "Chang") typ[i] = 1;
    else if(s == "Duan") typ[i] = 2;
    else if(s == "Tong") typ[i] = 3;
  }
  dfs1(1);
  int k = solve(1);
  if(k) {
    cout << "NO" << endl;
  }
  cout << "YES" << endl;
  for(int i = 2; i <= n; i++) {
    if(par[i] > i) cout << i << " " << par[i] << endl;
  }
}

int32_t main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cout << fixed << setprecision(9);
    int testes = 1;
    // cin >> testes;
    int test = 0;

    while(testes--) {
      // cout << "Case #" << (++test) << ": ";
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5828kb

input:

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

output:

YES
4 5
6 8

result:

ok Correct.

Test #2:

score: 0
Accepted
time: 3ms
memory: 6256kb

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
2 6
3 10
5 7
8 9

result:

ok Correct.

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 6372kb

input:

2
2 1 Tong

output:

NO
YES

result:

wrong output format Extra information in the output file