結果

問題 No.274 The Wall
ユーザー fiord
提出日時 2015-09-16 20:35:40
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 330 ms / 2,000 ms
コード長 1,974 bytes
コンパイル時間 1,495 ms
コンパイル使用メモリ 165,352 KB
実行使用メモリ 132,480 KB
最終ジャッジ日時 2024-06-22 02:06:36
合計ジャッジ時間 3,073 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:48:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         scanf("%d %d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:50:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         for(int i=0;i<n;i++)    scanf("%d %d",&l[i],&r[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> node[4010],rnode[4010];
int color[4010];
bool visited[4010];
int cnt=0;
vector<int> start;
bool cross(int a1,int a2,int b1,int b2){
    if(a1<=b1&&b1<=a2)  return true;
    if(a1<=b2&&b2<=a2)  return true;
    if(a1<=b1&&b2<=a2)  return true;
    if(b1<=a1&&a2<=b2)  return true;
    return false;
}
void dfs1(int now){
    visited[now]=true;
    for(int i=0;i<(int)node[now].size();i++){
        int next=node[now][i];
        if(!visited[next]){
            dfs1(next);
        }
    }
    start.push_back(now);
}
void rdfs(int now,int group){
    visited[now]=true;
    for(int i=0;i<(int)rnode[now].size();i++){
        int next=rnode[now][i];
        if(!visited[next])  rdfs(next,group);
    }
    color[now]=group;
}
void scc(){
    for(int i=0;i<4010;i++) visited[i]=false;
    start.clear();
    for(int i=0;i<2*n;i++){
        if(!visited[i]) dfs1(i);
    }
    for(int i=0;i<4010;i++) visited[i]=false,color[i]=0;
    int cnt=1;
    for(int i=(int)start.size()-1;i>=0;i--){
        if(!visited[start[i]])  rdfs(start[i],cnt++);
    }
}
    
int main(){
    scanf("%d %d",&n,&m);
    int l[n],r[n];
    for(int i=0;i<n;i++)    scanf("%d %d",&l[i],&r[i]);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(l[i]<=r[j]&&l[j]<=r[i]){
                node[2*i].push_back(2*j+1);
                rnode[2*j+1].push_back(2*i);
                node[2*j].push_back(2*i+1);
                rnode[2*i+1].push_back(2*j);
            }
            if(m-r[i]-1<=r[j]&&l[j]<=m-l[i]-1){
                node[2*i+1].push_back(2*j+1);
                rnode[2*j+1].push_back(2*i+1);
                node[2*j].push_back(2*i);
                rnode[2*i].push_back(2*j);
            }
            if(l[i]<=m-l[j]-1&&m-r[j]-1<=r[i]){
                node[2*i].push_back(2*j);
                rnode[2*j].push_back(2*i);
                node[2*j+1].push_back(2*i+1);
                rnode[2*i+1].push_back(2*j+1);
            }
            if(-r[i]<=-l[j]&&-r[j]<=-l[i]){
                node[2*i+1].push_back(2*j);
                rnode[2*j].push_back(2*i+1);
                node[2*j+1].push_back(2*i);
                rnode[2*i].push_back(2*j+1);
            }
        }
    }
    scc();
    for(int i=0;i<n;i++){
        if(color[2*i]==color[2*i+1]){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0