提出 #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 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| 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 |