結果

問題 No.1777 万華鏡美術館
ユーザー kiyoshi0205kiyoshi0205
提出日時 2021-12-06 13:52:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,022 bytes
コンパイル時間 3,389 ms
コンパイル使用メモリ 209,292 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 09:00:04
合計ジャッジ時間 3,555 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:62:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   62 |     for(auto& [l,r]:edge){
      |               ^
main.cpp:74:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   74 |     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;
int root;
bool dfs(int now){
  if(tree[now].empty())return false;
  int ch=(edge[now].second-edge[now].first-1)%2;
  bool f[2]={false,false};
  for(auto x:tree[now]){
    f[dfs(x)]=true;
    ch^=(edge[x].second-edge[x].first-1)%2;
  }
  if(f[1]&&(f[0]|ch)){
    puts("5");
    exit(0);
  }
  return f[0];
}
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;
    }
  }
  if(int(ver.size())==M){
    puts("4");
    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]);
  }
  root=edgenum[kukan[0]];
  if(dfs(root))puts("4");
  else puts("5");
}
0