結果

問題 No.2536 同値性と充足可能性
コンテスト
ユーザー twooimp2
提出日時 2023-11-10 22:47:29
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,442 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,709 ms
コンパイル使用メモリ 217,676 KB
最終ジャッジ日時 2025-02-17 21:17:03
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 17 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:54:15: warning: ‘kind’ may be used uninitialized [-Wmaybe-uninitialized]
   54 |       ll last,kind;
      |               ^~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using P=pair<ll,ll>;

int main(){
  ll n,m;
  cin>>n>>m;
  vector<vector<P>> G(n);
  for(ll i=0;i<m;i++){
    ll u,v;
    string e;
    cin>>u>>e>>v;
    u--;
    v--;
    if(e=="<==>"){
      G[u].push_back(P(v,1));
      G[v].push_back(P(u,1));
    }else{
      G[u].push_back(P(v,0));
      G[v].push_back(P(u,0));
    }
  }
  ll cnt=0;
  vector<ll> ans;
  vector<bool> seen(n,false);
  queue<ll> que;
  for(ll i=0;i<n;i++){
    if(!seen[i]&&G[i].size()==1){
      seen[i]=true;
      que.push(i);
      vector<vector<ll>> dp(n,vector<ll>(2,-1e18));
      dp[i][0]=0;
      dp[i][1]=1;
      while(que.size()){
        ll q=que.front();
        que.pop();
        for(P p:G[q]){
          ll u=p.first;
          ll idx=p.second;
          if(!seen[u]){
            seen[u]=true;
            if(idx==1){
              dp[u][0]=max(dp[u][0],dp[q][0]);
              dp[u][1]=max(dp[u][1],dp[q][1]+1);
            }else{
              dp[u][0]=max(dp[u][0],dp[q][1]);
              dp[u][1]=max(dp[u][1],dp[q][0]+1);
            }
          }
        }
      }
      ll tmp=-1e18;
      ll last,kind;
      for(ll i=0;i<n;i++){
        if(tmp<dp[i][0]){
          tmp=dp[i][0];
          last=i;
          kind=0;
        }
        if(tmp<dp[i][1]){
          tmp=dp[i][1];
          last=i;
          kind=1;
        }
      }
      vector<bool> seen2(n,false);
      seen2[last]=true;
      queue<P> que2;
      que2.push(P(last,kind));
      if(kind==1){
        ans.push_back(last);
      }
      while(que2.size()){
        P q=que2.front();
        que2.pop();
        ll ver=q.first;
        ll kind=q.second;
        for(P p:G[ver]){
          ll u=p.first;
          if(!seen2[u]){
            if(dp[u][0]+1==dp[ver][kind]){
              seen2[u]=true;
              que2.push(P(u,0));
              if(kind==1){
                ans.push_back(u);
              }
            }else if(dp[u][1]+1==dp[ver][kind]){
              seen2[u]=true;
              que2.push(P(u,1));
              if(kind==1){
                ans.push_back(u);
              }
            }
          }
        }
      }
    }
  }
  sort(ans.begin(),ans.end());
  ans.erase(unique(ans.begin(),ans.end()),ans.end());
  if(ans.size()<(n+1)/2){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
    cout<<ans.size()<<endl;
    for(ll u:ans){
      cout<<u+1<<" ";
    }
    cout<<endl;
  }
}
0