結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー TKTYI
提出日時 2025-02-21 22:14:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 1,694 bytes
コンパイル時間 4,491 ms
コンパイル使用メモリ 302,980 KB
実行使用メモリ 33,068 KB
最終ジャッジ日時 2025-02-21 22:14:17
合計ジャッジ時間 10,178 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from main.cpp:1:
In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = bool&; _T1 = int; _T2 = bool]’,
    inlined from ‘constexpr std::pair<typename std::__strip_reference_wrapper<typename std::decay<_Tp>::type>::__type, typename std::__strip_reference_wrapper<typename std::decay<_Tp2>::type>::__type> std::make_pair(_T1&&, _T2&&) [with _T1 = int&; _T2 = bool&]’ at /usr/include/c++/13/bits/stl_pair.h:927:14,
    inlined from ‘int main()’ at main.cpp:53:31:
/usr/include/c++/13/bits/stl_pair.h:317:42: warning: ‘inv’ may be used uninitialized [-Wmaybe-uninitialized]
  317 |         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y))
      |                                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:39:22: note: ‘inv’ was declared here
   39 |                 bool inv;
      |                      ^~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int M;cin>>M;
	vector<int>A(M),B(M),C(M);
	rep(i,0,M)cin>>A[i]>>B[i]>>C[i];
	{
		set<pair<int,pii>>S;
		rep(i,0,M)S.insert(make_pair(A[i],pii(B[i],C[i])));
		if(sz(S)<M){cout<<"NO"<<endl;return 0;}
	}
	vector<pii>E;
	rep(i,0,M){
		E.emplace_back(pii(A[i],B[i]));
		E.emplace_back(pii(B[i],C[i]));
		E.emplace_back(pii(A[i],C[i]));
	}
	sort(all(E));
	E.erase(unique(all(E)),E.end());
	int L=sz(E);
	vector<vector<int>>F(L);
	rep(i,0,M){
		F[lower_bound(all(E),pii(A[i],B[i]))-E.begin()].emplace_back(i);
		F[lower_bound(all(E),pii(B[i],C[i]))-E.begin()].emplace_back(i);
		F[lower_bound(all(E),pii(A[i],C[i]))-E.begin()].emplace_back(i);
	}
	vector<vector<pair<int,bool>>>es(M);
	rep(i,0,L)rep(j,0,sz(F[i])-1){
		if(sz(F[i])>2){cout<<"NO"<<endl;return 0;}
		int u=F[i][j],v=F[i][j+1];
		bool inv;
		if(A[u]==A[v]){
			if(B[u]==B[v]||C[u]==C[v])inv=1;
			else inv=0;
		}
		else if(A[u]==B[v]){
			if(B[u]==C[v])inv=1;
			else inv=0;
		}
		else if(B[u]==B[v])inv=1;
		else if(B[u]==A[v]){
			if(C[u]==B[v])inv=1;
			else inv=0;
		}
		es[u].emplace_back(make_pair(v,inv));
		es[v].emplace_back(make_pair(u,inv));
	}
	bool ok=1;
	vector<bool>pot(M),seen(M);
	function<void(int)>dfs=[&](int v){
		seen[v]=1;
		for(auto[u,b]:es[v]){
			if(!seen[u]){pot[u]=(pot[v]^b);dfs(u);}
			else if(pot[u]!=(pot[v]^b))ok=0;
		}
	};
	rep(i,0,M)if(!seen[i])dfs(i);
	if(ok)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
0