結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー Andrew8128
提出日時 2025-02-21 23:30:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,661 bytes
コンパイル時間 3,998 ms
コンパイル使用メモリ 308,628 KB
実行使用メモリ 99,136 KB
最終ジャッジ日時 2025-02-21 23:31:12
合計ジャッジ時間 18,004 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  int idx_cnt = 0;
  for(auto [k, e] : cnt){
    if(e >= 3){
      cout << "NO\n";
      exit(0);
    }
    xdi[size(idx)] = k;
    idx[k] = idx_cnt;
    idx_cnt++;
  }
  int N = idx_cnt;
  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]);
      G[to[2]].push_back(to[1]);
    }
    if(to[0] != -1 && to[2] != -1){
      G[to[0]].push_back(to[2]);
      G[to[2]].push_back(to[0]);
    }
  }
  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)]);
      }
    }
  }

  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
*/
0