結果
問題 | No.479 頂点は要らない |
ユーザー |
![]() |
提出日時 | 2017-01-27 23:22:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 95 ms / 1,500 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 885 ms |
コンパイル使用メモリ | 82,700 KB |
実行使用メモリ | 9,424 KB |
最終ジャッジ日時 | 2024-12-23 17:00:18 |
合計ジャッジ時間 | 3,371 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #define pb push_back #define pii pair<int,int> using namespace std; int main(void){ int n,m; int a,b,i,j; vector<vector<int> >edge; cin>>n>>m; int use[n]; for(i=0;i<n;i++){ vector<int> x; edge.pb(x); use[i]=0; } for(i=0;i<m;i++){ cin>>a>>b; edge[a].pb(b); edge[b].pb(a); } for(i=n-1;i>=0;i--){ if(edge[i].size()!=0 && use[i]==0){ use[i]=-1; for(j=0;j<edge[i].size();j++){ use[edge[i][j]]=1; auto itr=find(edge[edge[i][j]].begin(),edge[edge[i][j]].end(),i); if(itr!=edge[edge[i][j]].end()) edge[edge[i][j]].erase(itr); } } } /* cout<<endl; for(i=0;i<n;i++){ cout<<i<<":"; for(j=0;j<edge[i].size();j++){ cout<<edge[i][j]<<" "; } cout<<endl; } */ j=0; for(i=n;i>=0;i--){ if(use[i]==1) j=1; if(use[i]==1&&j==1) cout<<1; if(use[i]!=1&&j==1) cout<<0; } cout<<endl; return 0; }