提出 #40446437


ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
#define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int,null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update>order_set;
typedef pair<int,int>pr;
#define all(i)     i.begin() , i.end()
#define ft     first
#define sn     second
#define pb push_back


#define en "\n"
#define dbg cout<<"rony\n";

#define MAXN 200010
#define inf 1e9
const ll mod = 1e9+7;

void solve()
{
    ll n;
    cin >> n;
    ll a[n];
    for(ll i = 0;i < n;i++) cin >> a[i];
    
    vector<string>v(n);

    for(ll i = 0;i < n;i++) cin >> v[i];
    
    vector<vector<ll>>dist(n,vector<ll>(n,inf));
    vector<vector<ll>>value(n,vector<ll>(n));

    for(ll i = 0;i < n;i++){
        for(ll j = 0;j < n;j++){
            if(i == j && v[i][j] == 'Y'){
                dist[i][j] = 0;
                value[i][j] = a[i];
            }
            if(i != j && v[i][j] == 'Y'){
                dist[i][j] = 1;
                value[i][j] = a[i] + a[j];
            }
        }
    }

    // floyed warshell
    for(ll k = 0;k < n;k++){
        for(ll i = 0;i < n;i++){
            for(ll j = 0;j < n;j++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                   dist[i][j] = dist[i][k] + dist[k][j];
                   value[i][j] = value[i][k] + value[k][j] - a[k];
                }
                if(dist[i][j] == dist[i][k] + dist[k][j]){
                    if(value[i][j] < value[i][k] + value[k][j] - a[k]){
                        value[i][j] = value[i][k] + value[k][j] - a[k];
                    }
                }
            }
        }
    }

    ll q;
    cin >> q;
    while(q--)
    {
        ll s,t;
        cin >> s >> t; s--,t--;
        if(dist[s][t] == inf) cout<<"Impossible\n";
        else cout<<dist[s][t]<<" "<<value[s][t]<<en;

    }
}
int main()
{
    IOS;
   int t;
   t = 1;

   // cin >> t;
   int c = 0;
    while ( t-- )
    {
        //cout<<"Case "<<++c<<": ";
        solve();
    }
    return 0;
}   

提出情報

提出日時
問題 E - Souvenir
ユーザ ar_rony1
言語 C++ (GCC 9.2.1)
得点 500
コード長 2250 Byte
結果 AC
実行時間 104 ms
メモリ 4740 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:8: warning: unused variable ‘c’ [-Wunused-variable]
   89 |    int c = 0;
      |        ^

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 46
セット名 テストケース
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt
ケース名 結果 実行時間 メモリ
example_00.txt AC 6 ms 3504 KiB
example_01.txt AC 2 ms 3508 KiB
hand_00.txt AC 71 ms 4720 KiB
hand_01.txt AC 68 ms 4676 KiB
hand_02.txt AC 58 ms 4644 KiB
hand_03.txt AC 69 ms 4648 KiB
hand_04.txt AC 5 ms 3556 KiB
random_00.txt AC 61 ms 4588 KiB
random_01.txt AC 62 ms 4692 KiB
random_02.txt AC 64 ms 4680 KiB
random_03.txt AC 62 ms 4736 KiB
random_04.txt AC 60 ms 4720 KiB
random_05.txt AC 73 ms 4740 KiB
random_06.txt AC 64 ms 4720 KiB
random_07.txt AC 66 ms 4644 KiB
random_08.txt AC 54 ms 4684 KiB
random_09.txt AC 59 ms 4592 KiB
random_10.txt AC 55 ms 4736 KiB
random_11.txt AC 60 ms 4592 KiB
random_12.txt AC 57 ms 4720 KiB
random_13.txt AC 55 ms 4716 KiB
random_14.txt AC 73 ms 4696 KiB
random_15.txt AC 79 ms 4696 KiB
random_16.txt AC 55 ms 4592 KiB
random_17.txt AC 54 ms 4648 KiB
random_18.txt AC 82 ms 4740 KiB
random_19.txt AC 83 ms 4740 KiB
random_20.txt AC 83 ms 4716 KiB
random_21.txt AC 65 ms 4720 KiB
random_22.txt AC 82 ms 4740 KiB
random_23.txt AC 66 ms 4740 KiB
random_24.txt AC 66 ms 4624 KiB
random_25.txt AC 70 ms 4724 KiB
random_26.txt AC 68 ms 4656 KiB
random_27.txt AC 72 ms 4648 KiB
random_28.txt AC 62 ms 4684 KiB
random_29.txt AC 66 ms 4736 KiB
random_30.txt AC 72 ms 4644 KiB
random_31.txt AC 55 ms 4644 KiB
random_32.txt AC 55 ms 4736 KiB
random_33.txt AC 55 ms 4644 KiB
random_34.txt AC 63 ms 4724 KiB
random_35.txt AC 78 ms 4692 KiB
random_36.txt AC 77 ms 4648 KiB
random_37.txt AC 104 ms 4644 KiB
random_38.txt AC 102 ms 4720 KiB