Submission #00016
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<bits/stdc++.h> using namespace std; int find( int x); int same( int x, int y); void unite( int x, int y); vector< int >nw[100009]; vector< int >nh[100009]; int p[100009]; int main(){ int h,w,n; cin>>h>>w>>n; for ( int i=1;i<=n;i++){ int x,y; cin>>x>>y; nw[y].push_back(i); nh[x].push_back(i); p[i]=i; } for ( int i=1;i<=h;i++){ for ( int j=0;j<( int )nw[i].size()-1;j++){ int a=nw[i][j]; int b=nw[i][j+1]; if (!same(a,b)){ unite(a,b); } } } for ( int i=1;i<=w;i++){ for ( int j=0;j<( int )nh[i].size()-1;j++){ int a=nh[i][j]; int b=nh[i][j+1]; if (!same(a,b)){ unite(a,b); } } } int q; cin>>q; for ( int i=0;i<q;i++){ int s,g; cin>>s>>g; if (same(s,g)){ cout<< "yes" <<endl; } else { cout<< "no" <<endl; } } return (0); } int find( int x){ if (p[x]==x) return x; return p[x]=find(p[x]); } int same( int x, int y){ if (find(x)==find(y)) return 1; return 0; } void unite( int x, int y){ x=find(x); y=find(y); p[x]=y; } |
ステータス
項目 | データ |
---|---|
問題 | 0010 - PROBOT |
ユーザー名 | r1705 |
投稿日時 | 2019-04-24 18:46:09 |
言語 | C++11 |
状態 | Accepted |
得点 | 100 |
ソースコード長 | 1124 Byte |
最大実行時間 | 301 ms |
最大メモリ使用量 | 12608 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 100 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
input-sample1 | AC | 23 ms | 5212 KB |
1
|
input01 | AC | 238 ms | 5608 KB |
1
|
input02 | AC | 228 ms | 5996 KB |
1
|
input03 | AC | 220 ms | 6252 KB |
1
|
input04 | AC | 262 ms | 8172 KB |
1
|
input05 | AC | 268 ms | 8980 KB |
1
|
input06 | AC | 266 ms | 9700 KB |
1
|
input07 | AC | 289 ms | 10692 KB |
1
|
input08 | AC | 294 ms | 11584 KB |
1
|
input09 | AC | 301 ms | 12608 KB |
1
|