同時検索と高速読み取りおよび高速書き込み



Concurrent Search Fast Reading



質問から紹介する トピックリンク

はい
はい
しない



これは、チェックボードを組み合わせたサブ質問です。
名前が示すように、複合検索はコレクションを検索してマージすることであり、2つの主要な機能があります。

機能の検索:

一般的な執筆

int find(int root) { int tmp,son son=root while(root!=pre[root])//Search until the root node appears { root=pre[root] } //root is already the root node while(son!=root)//Path compression { tmp=pre[son] pre[son]=root//Unify the parent nodes of elements belonging to the same set as the root node son=tmp } return root//Find the root node }

ゲーム終了後に時間のかかるコードを確認したところ、検索機能を最適化できることがわかりました。



最適化された書き込み

int find(int root) { return root==pre[root]?root:pre[root]=find(pre[root]) }

画像
これは少し速いです〜

結合機能:

void setu(int x,int y) { int a=xfind(x),b=xfind(y)//Find the respective root nodes of the two connected elements if(a!=b)//If not the same pre[a]=b//Direct merge }

次に、この質問のACコードを添付します。

#include using namespace std int pre[50005] int xfind(int root) { return root==pre[root]?root:pre[root]=xfind(pre[root]) } void setu(int x,int y) { int a=xfind(x),b=xfind(y) if(a!=b) pre[a]=b } int main() { int n,m,p cin>>n>>m>>p for(int i=1i<=ni++) { pre[i]=i } while(m--) { int a,b scanf('%d%d',&a,&b) setu(a,b) } while(p--) { int a,b scanf('%d%d',&a,&b) if(xfind(a)!=xfind(b)) printf('No ') else printf('Yes ') } return 0 }

画像
上記のコードの時間はすでに非常に短いですが、最短時間でdalaoのコードを調べたところ、彼はまだ高速の読み取りと書き込みを使用していることがわかりました。
変更したコードを以下に添付します。



#include using namespace std int pre[50005] void get(int &x)//Fast reading void put(int x)//Write fast { int num = 0 char c[15] while(x) c[++num] = (x%10)+48, x /= 10 while(num) putchar(c[num--]) putchar(' ') } int xfind(int root) { return root==pre[root]?root:pre[root]=xfind(pre[root]) } void setu(int x,int y) { int a=xfind(x),b=xfind(y) if(a!=b) pre[a]=b } int main() { int n,m,p,a,b get(n) get(m) get(p) for(int i=1i<=ni++) { pre[i]=i } while(m--) { get(a)get(b) setu(a,b) } while(p--) { get(a)get(b) if(xfind(a)!=xfind(b)) printf('No ') else printf('Yes ') } return 0 }

画像
それはほとんど失われていますか...

今回の書き方はかなり面倒で、自分でボードを覚えることが大事です。同時に、ゲーム終了後は、他の人のACコードをもっと見て、他の人がどのように書いているかを学び、マスターが自分とどのように違うかを見て、良いことを学ぶ(盗む)ことができることを理解しています。