#1045139 (C++23) No.3031 曲面の向き付け

• 問題: No.3031 曲面の向き付け
• ユーザー: Andrew8128
• 提出日時: 2025-02-21 23:25:05
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 2,642 bytes
• コンパイル時間: 4,216 ms
• コンパイル使用メモリ: 310,300 KB
• 実行使用メモリ: 46,088 KB
• 最終ジャッジ日時: 2025-02-21 23:25:18
• 合計ジャッジ時間: 12,249 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 27 WA * 2

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct UnionFind {
  vector<int> p;
  UnionFind(int n):p(n,-1){}
  int find(int x){
    if(p[x] < 0) return x;
    return p[x] = find(p[x]);
  }
  bool unite(int x,int y) {
    x = find(x);
    y = find(y);
    if(x == y)return false;
    if(p[x] > p[y])swap(x,y);
    p[x] += p[y];
    p[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -p[find(x)];}
};
int main(){
  int M;
  cin >> M;
  vector<array<int, 3>> ABC(M);
  map<array<int, 2>, int> cnt;
  for (int i = 0; i < M; i++) {
    cin >> ABC[i][0] >> ABC[i][1] >> ABC[i][2];
    cnt[{ABC[i][0], ABC[i][1]}]++;
    cnt[{ABC[i][1], ABC[i][2]}]++;
    cnt[{ABC[i][0], ABC[i][2]}]++;
  }
  map<array<int, 2>, int> idx;
  map<int, array<int, 2>> xdi;
  for(auto [k, e] : cnt){
    if(e >= 3){
      cout << "NO\n";
      exit(0);
    }
    if(e == 2){
      xdi[size(idx)] = k;
      idx[k] = size(idx);
    }
  }
  int N = size(idx);
  vector<vector<int>> G(N);
  UnionFind uf(N);
  for (int i = 0; i < M; i++) {
    vector<int> to(3, -1);
    if(idx.contains({ABC[i][0], ABC[i][1]})){
      to[0] = idx[{ABC[i][0], ABC[i][1]}];
    }
    if(idx.contains({ABC[i][1], ABC[i][2]})){
      to[1] = idx[{ABC[i][1], ABC[i][2]}];
    }
    if(idx.contains({ABC[i][0], ABC[i][2]})){
      to[2] = idx[{ABC[i][0], ABC[i][2]}];
    }
    if(to[0] != -1 && to[1] != -1){
      uf.unite(to[0], to[1]);
    }
    if(to[1] != -1 && to[2] != -1){
      G[to[1]].push_back(to[2]);
    }
    if(to[0] != -1 && to[2] != -1){
      G[to[0]].push_back(to[2]);
    }
  }
  map<int, int> m;
  int tmp = 0;
  for (int i = 0; i < N; i++) {
    if(uf.find(i) == i){
      m[i] = tmp;
      tmp++;
    }
  }
  vector<vector<int>> H(tmp);
  for (int i = 0; i < N; i++) {
    for(int j : G[i]){
      if(uf.same(i, j)){
        cout << "NO\n";
        exit(0);
      }else{
        H[m[uf.find(i)]].push_back(m[uf.find(j)]);
        H[m[uf.find(j)]].push_back(m[uf.find(i)]);
      }
    }
  }
  vector<int> color(tmp, -1);
  for (int i = 0; i < tmp; i++) {
    if(color[i] == -1){
      queue<int> q;
      color[i] = 1;
      q.push(i);
      while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int to : H[now]) {
          if (color[to] == -1) {
            color[to] = 1 - color[now];
            q.push(to);
          } else if (color[to] == color[now]) {
            cout << "NO\n";
            exit(0);
          }
        }
      }
    }
  }
  cout << "YES\n";
  return 0;
}
/*
  File : ~/yukicoder/528/E.cpp
  Date : 2025/02/21
  Time : 22:31:48
*/
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX