結果
問題 | No.1777 万華鏡美術館 |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-12 23:00:40 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 3,153 ms |
コード長 | 1,472 bytes |
コンパイル時間 | 3,801 ms |
コンパイル使用メモリ | 120,496 KB |
最終ジャッジ日時 | 2025-01-26 09:27:32 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) int N; int M; vector<int> num_edges; vector<vector<int>> E; int main() { int ans = 4; cin >> N; cin >> M; E.resize(N); num_edges.assign(N, 0); rep(i,M){ int u,v; cin >> u >> v; u--; v--; E[v].push_back(u); num_edges[u]++; num_edges[v]++; } rep(i,N) if(num_edges[i] % 2 == 1) ans = 5; rep(i,N) sort(E[i].rbegin(), E[i].rend()); vector<int> vertices = { 0 }; vector<int> face_colors = { 0 }; for(int p=1; p<N; p++){ for(int e : E[p]){ int num_vertices = 2; int color = 1 - face_colors.back(); while(true){ if(vertices.back() <= e) break; num_vertices++; vertices.pop_back(); face_colors.pop_back(); if(color == face_colors.back()) ans = 5; } if(num_vertices % 2 == 1 && color != 0) ans = 5; if(vertices.back() == e){ face_colors.back() = color; } else{ vertices.push_back(e); face_colors.push_back(color); } } vertices.push_back(p); face_colors.push_back(0); } { int num_vertices = vertices.size(); int color = 1; if(num_vertices % 2 == 1) ans = 5; for(auto c : face_colors) if(c == color) ans = 5; } cout << ans << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;