結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 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; | ^~~
ソースコード
#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; }