結果

問題 No.1777 万華鏡美術館
コンテスト
ユーザー kiyoshi0205
提出日時 2021-12-06 12:59:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,875 bytes
コンパイル時間 2,611 ms
コンパイル使用メモリ 210,692 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 08:55:19
合計ジャッジ時間 3,069 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   56 |     for(auto& [l,r]:edge){
      |               ^
main.cpp:68:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   68 |     auto [l,r]=x;
      |          ^

ソースコード

diff # 

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> tree;
vector<pair<int,int>>edge;
bool dfs(int now){
  int ch=(edge[now].second-edge[now].first)%2;
  bool f=false;
  for(auto x:tree[now]){
    f|=dfs(x);
    ch^=(edge[x].second-edge[x].first)%2;
  }
  if(ch&f){
    puts("5");
    exit(0);
  }
  return ch;
}
int main(){
  int i,N,M;
  cin>>N>>M;
  tree.resize(M);
  edge.resize(M);
  if(M==0){
    putchar('4'+N%2);
    putchar('\n');
    return 0;
  }
  vector<int> ver;
  map<pair<int,int>,int> edgenum;
  for(int i=0;i<M;++i){
    int u,v;
    cin>>u>>v;
    --u;--v;
    edge[i]=pair<int,int>(u,v);
    edgenum[edge[i]]=i;
    ver.emplace_back(u);
    ver.emplace_back(v);
  }
  sort(ver.begin(),ver.end());
  ver.erase(unique(ver.begin(),ver.end()),ver.end());
  for(size_t i=0;i<ver.size();++i){
    if(!edgenum.count(minmax(ver[i],ver[(i+1)%ver.size()]))){
      puts("5");
      return 0;
    }
    if((ver[(i+1)%ver.size()]+N-ver[i])%N%2!=1){
      puts("5");
      return 0;
    }
  }
  {
    edgenum.clear();
    for(auto& [l,r]:edge){
      l=lower_bound(ver.begin(),ver.end(),l)-ver.begin();
      r=lower_bound(ver.begin(),ver.end(),r)-ver.begin();
    }
    for(int i=0;i<M;++i)edgenum[edge[i]]=i;
  }
  vector<pair<int,int>> kukan=edge;
  sort(kukan.begin(),kukan.end(),[](pair<int,int> l,pair<int,int> r){
    return l.first!=r.first?l.first<r.first:l.second>r.second;
  });
  vector<pair<int,int>> rootlis;
  for(auto x:kukan){
    auto [l,r]=x;
    if(rootlis.empty()){
      rootlis.emplace_back(x);
      continue;
    }
    while(rootlis.size()&&rootlis.back().second<=l)rootlis.pop_back();
    assert(rootlis.size());
    tree[edgenum[rootlis.back()]].emplace_back(edgenum[x]);
  }
  const int root=edgenum[kukan[0]];
  dfs(root);
  puts("4");
}
0