🌲UFT🌲

B - 駐車場

 

  1. #include<bits/stdc++.h>
  2. #define int long long int
  3. using namespace std;
  4.  
  5. static const int INF = 1LL << 60;
  6. static const int MAX_N = 200005;
  7.  
  8. int N;
  9. struct UF {
  10. int n, par[MAX_N];
  11. ///最初は全部根。
  12. void init(int pn){
  13. n = pn;
  14. for(int i=0;i<n;i++)par[i]=i;
  15. }
  16. ///木の根を求める
  17. int find(int x){
  18. if(par[x]==x){
  19. return x;
  20. }else{
  21. return par[x] = find(par[x]);
  22. }
  23. }
  24. ///xとyの属する集合を併合
  25. void unite(int x,int y){
  26. x = find(x);
  27. y=find(y);
  28. if(x==y)return;
  29.  
  30. par[x] = y;
  31. }
  32. ///xとyが同じねに属するか?
  33. bool same(int x,int y){
  34. return find(x)==find(y);
  35. }
  36. };
  37. ///グラフがつながっているか知りたいとき(例ARC056-Bの)
  38.  
  39. int m, s, ans[MAX_N];
  40. vector<int> G[MAX_N];
  41. UF uf;
  42. int n;
  43.  
  44. signed main(){
  45. ///cinの高速化
  46. cin.tie(0);
  47. ios::sync_with_stdio(false);
  48.  
  49. cin >> n >> m >> s;
  50. uf.init(n);
  51.  
  52. for(int i = 0; i < m; i++){
  53. int u,v;
  54. cin >> v >> u;
  55. G[u].push_back(v);
  56. ///無向グラフ
  57. G[v].push_back(u);
  58. }
  59. ///大きい方から?!(小さい方は埋まってるから.)
  60. for(int i = n; 0 < i; --i){
  61. for(int j=0; j < G[i].size(); j++){
  62. int to = G[i][j];
  63. if(to < i)continue;
  64. uf.unite(i, to);
  65. }
  66. ans[i] = uf.same(i, s);
  67. }
  68. for(int i = 1; i <= n; i++){
  69. if(!ans[i])continue;
  70. cout << i << endl;
  71. }
  72.  
  73. return 0;
  74. }

 

 

幅優先探索?!

広義昨日解いたチーズについてです

初めて幅優先探索書きました

もちろんあり本に頼りつつ

せっかくなので自分のためにコード八説きます

にゃにゃにゃにゃ

typedef pair<int ,int> P;
char masu[1003][1003];
int W,H,K,ans=0;
int sx[10],sy[10];
int gx[10],gy[10];
 
int d[1003][1003];
 
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
 
queue<P> que;
 
void sho(){
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            d[j][i]=INF;
        }
    }
    while(que.size()){
        que.pop();
    }
}
 
int bfs(){
    for(int i=0;i<K;i++){
        sho();
        que.push(P(sx[i],sy[i]));
        d[sx[i]][sy[i]]=0;
        while(que.size()){
            P p=que.front();que.pop();
            if(p.first==gx[i+1]&&p.second==gy[i+1])break;
            for(int j=0;j<4;j++){
                int nx = p.first+dx[j],ny = p.second+dy[j];
                if(0<=nx&nx<W&&0<=ny&&ny<H&&masu[nx][ny]!='X'&&d[nx][ny]==INF){
                    que.push(P(nx,ny));
                    d[nx][ny] = d[p.first][p.second] + 1;
                }
            }
        }ans+=d[gx[i+1]][gy[i+1]];
    }
    return ans;
}
 
signed main(){
    cin >> H >> W >> K;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> masu[j][i];
            int a=masu[j][i]-'0';
            if(isdigit(masu[j][i])){
                gx[a]=j,gy[a]=i,sx[a]=j,sy[a]=i;
            }else if(masu[j][i]=='S'){
                sx[0]=j,sy[0]=i;
            }
        }
    }
    int answer = bfs();
    cout << answer << endl;
return 0;
}

小鳥が泣いたよほけきょ🐓

 

ーーーーーーー❀おまけ❀ーーーーーーーー

最初書いた、幅を知らず、つよしさん達に教えてもらう前のコード

貼っときます

#include<bits/stdc++.h>
#include<ctype.h>
#define int long long int
#define rep(a,b) for(int a=0;a<b;a++)
#define INF 1000006
using namespace std;
 
int tx[] = {1,0,-1,0};
int ty[] = {0,1,0,-1};
int w,h,che,sx,sy;
char bases;
int base[1003][1003],base2[1003][1003],memo[1003][1003];
 
int chee(int x,int y,int n){
    int ans=INF;
    if(memo[x][y]>0&&(memo[x][y]!=INF||base[x][y]<0))return memo[x][y];
    else if(base[x][y]==n)return 0;
    else if(base[x][y]>=0){
        base[x][y]=-1;
        for(int i=0;i<4;i++){
            if(x+tx[i]>=0&&x+tx[i]<w&&y+ty[i]>=0&&y+ty[i]<h){
                ans = min(ans,chee(x+tx[i],y+ty[i],n)+1);
            }
        }base[x][y]=0;
    }
    memo[x][y]=ans;
    return ans;
}
void sho(int b[1003][1003],int a[1003][1003]){
    rep(i,1003){
        rep(j,1003){
            b[i][j]=a[i][j];
        }
    }
}
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int zx[20],zy[20];
    cin >> h >> w >> che;
    rep(f,h){
        rep(s,w){
            cin >> bases;
            switch(bases){
                case 'S':sx=s;sy=f;
                case '.':base[s][f]=0;
                break;
                case 'X':base[s][f]=-1;
                break;
                default:{base[s][f]=bases - '0';
                        zx[base[s][f]]=s;
                        zy[base[s][f]]=f;
                        }
 
            }
        }
    }
    sho(base2,base);
    int ans=0;
    ans+=chee(sx,sy,1);
    for(int i=2;i<=che;i++){
        sho(base,base2);
        fill((int*)memo,(int*)(memo+1003),0);
        ans+=chee(zx[i-1],zy[i-1],i);
    }
    cout << ans << endl;
return 0;
}

 上のコードの感想は、「強引」ですね★★

 

ただ今の時刻4時半です良い子は寝ましょう。

 

補足::コメント何かしらあったらお願いです~★★

ドロドロした自己紹介★

あばばばばばばばふなちです🍤

今日は今回の席次も一昨日(広義昨日)分かったことだし、

今まで自分がしてきたことについて書こうとね、

今まで日記ですね~(´・ω・)(・ω・`)ネー

 

途中までざっくりいうと、

生まれた

小学生になった

中学で真面目にノーマルに試験勉強して、(いやー今だったらありえない。あっけど1日アニメ2~3本見る習慣は守ってた!!)

修○館高校を受験しろという周りの声を無視して(英シンかよてったからね、)

国語したくなくてK高専を受けてなんか受かった

推薦だったから2か月くらい料理したりちょっと勉強するって感じだった

1年生の前期は真面目ちゃんしてたぞ。

数学と中間テスト怖いくらいに頑張ったぞいぞい!!お陰で、席次はTOPとれたv

1年の夏は遊んでたテニス部のみんなと海行ったりとかしてた青春してた?らしい

いいだろッ(´▽`)ウソデス...

f:id:hanahanahunachi:20160630014724p:plain

今となってはもう薄い記憶。ちなみにテニスは沢山練習して小さな大会(40人くらいの)でベスト4になったっす!!🎾

1年の秋ぐらいから不真面目になって勉強サボり始めた←なんか勉強をなめ始めた。

ていうか疲れたんだよ受験勉強からさまじめにやってきてさ分かるよね(分からないよね。うん、言い訳はよくない)で、スシローでバイトを始めた。初めて知ったんだけど、すし屋のバイト異臭を放つ覚悟と給料を交換してるって感じだよ、ほんまくさい、食べてるだけの人にはわかんないだろうけどほんとに🐡だから。まあけっちょく3か月でスシローとはバイバイした👐

あ、あとですね、

この頃、初冬に"JOI"という大会があるという事を知ったんです。←my BIG Incident!

これまでテニス部とプロラボ部を兼部していたため、

というかそれまでほぼプロラボ部に行ってなかったっすにゃ。

JOI一か月前くらいからプログラミングの勉強をちゃんとするようになった

その結果間違えて問題提出したのもあって見事2完すらできなかった

そのあとプロラボ部に行くようになってちょっと部員の人たちとしゃべれるようになったので、MonoGameでゲームを作るのに入れてもっらた!

ゲドさんとつよっしーさんがしようとしててカービーが誘われてたのに強引に入れてもらった感じ C#全く書けなかったからゲドさん達にはすごい沢山迷惑かけた

結局なんか中途半端な感じになってしまった後悔してる

f:id:hanahanahunachi:20160630021652p:plainf:id:hanahanahunachi:20160630021546p:plain

そのあとなにしたっけ忘れた、けど前よりは

競技プログラミングするようになった 進歩進歩⚡⚡

後期期末試験も1週間前くらいからぼちぼち頑張った。

で、待ちに待ったSpring休みに入りましたが、

なぜかバイトを始めてしまいました()今回はサイゼのホール🎂

でも、春休みで、簡単なdpを解けるようになりました(このころ私は弥生人だった🌵)

バイトで稼いだお金で、カービーと3泊4日の大阪神戸旅行をしました^^!!

いやーいいデートだったよ💛

その後にした大きな出来事(イベント)としては、

プロコンの企画書を頑張って書いて、みんなと気軽に話せるようになれたことがすごいうれしくて部活に行くのが楽しくなりました(´`*)あとは、

ハッカソン(Spajam)に出たことですかね、、

Android Stdioでの開発をJava全く書けなかったのですが試験前1~2週間の深夜(4時くらいまで)頑張って勉強しました✊

本番ではQRコードのTaskをもらったもですができませんでした()

あ、あ、ああああああああああああああああああああああ泣ぃ.

結果はどうあれ、魔剤を初めて飲めたしいい経験になりました(`・ω・´)!

その次の日(前日ほぼ徹夜?なの)に英語と物理のテストが待ち受けていたわけですよね、英語は単語わかんないままテスト受けて、crimateを候補者と訳したりとかへまべっかりしました(70点台をたたき出した)、物理は普通に説いたら解けた。

まあ、自分をぎりぎりまで追い詰めるのは楽しいですよね☆☆

で、今に至るわけですが、春から一層授業で爆睡するようになってしまいまして、

この頃友達に真面目に心配されています。平常点が真面目に悪いですよそう

あ、ちなみになんかほんとにわかんないんですけど、

席次またTOPいただきましたほんとよくわからん。まあこれで親に怒られなくて済むわけですよ(●´ω`●!)

 

今はXamarin開発と競プロ頑張ってるつもりかな..

数学・物理とかみんなより圧倒的にできてないのでね努力できるようになりたい。

そして頭がないので頭欲しい ほんと悲しい今日幅優先を初めて書いたしパスタが、ケース1までしか通らないしうおおおおおって感じ、

もしここまで読んでくれてる人いたらありがとうございます!!

f:id:hanahanahunachi:20160627232752j:plainf:id:hanahanahunachi:20160630024831p:plainf:id:hanahanahunachi:20160630024736p:plain

とりあえず、

これからも!ふなち!とよろしくです!!!!

動的計算法

初めてのブローグ(twitter風に)

とりあえずテスト的な感じで...今日ですね、

Crossing Black Ice

なんか解けてなかったので(難易度5出し簡単なの。)

#include<bits/stdc++.h>
#include<ctype.h>
#define int long long int
#define rep(a,b) for(int a=0;a<b;a++)
 
using namespace std;
 
int tx[] = {1,0,-1,0};
int ty[] = {0,1,0,-1};
int w,h,chee,sx,sy;
char bases;
int base[1003][1003];
 
int ice(int x,int y){
    int ans=0;
    if(base[x][y]){
        base[x][y]=0;
        for(int i=0;i<4;i++){
            if(x+tx[i]>=0&&x+tx[i]<w&&y+ty[i]>=0&&y+ty[i]<h){
                ans = max(ans,ice(x+tx[i],y+ty[i])+1);
            }
        }
        base[x][y]=1;
 
    } return ans;
}
 
signed main(){
    while(1){
        cin >> w >> h;
        if(!w||!h)break;
        rep(f,h){
            rep(s,w){
                cin >> base[s][f];
            }
        }
        int ans=0;
        rep(f,h){
            rep(s,w){
                if(base[s][f]){
                    ans = max(ans,ice(s,f));
                }
            }
        }
        cout << ans << endl;
    }
return 0;
}

 

 汚いコードだなーって感じ。

ちなみに0しか出力されないという悲しい事件が起きたのだが

入力読み取り時のとこで”base[s][w]”と書いてた⚓

ケアレスは怖いよ

今日のプログラミングの小テストで1/5点しか取れなかったのもね、うん、