2014-2015 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
===
比賽鏈結
---
https://codeforces.com/gym/100827
比賽影片
---
{%youtube mQ9mnd-kkPA%}
記分板
---
題解
---
### A. Runes
---
#### 題目摘要
給一個方程式，當中有一種數字(0到9)是未知的(表示為?)，求滿足式子的最小數字(輸入保證無前綴0或-0，並且?不能是前綴零)
#### 想法
從小到大枚舉可行數字並看是否符合式子
(題目看錯，從前期黑到後期QAQ
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
void solve() {
string s;
cin >> s;
int n=s.size();
vector<bool> vis1(10, 0);
for(int i=0;i<n;i++){
if (isdigit(s[i])) vis1[s[i] - '0'] = 1;
}
for(int d=0;d<10;d++) if (!vis1[d]){
bool f1=0, f2=0, f3=0;
ll num1=0, num2=0, num3=0;
int phlag=0;
int type=-1;
bool z1=0, z2=0, z3=0;
for(int i=0;i<n;i++){
if (i==0&&s[i]=='-'){
f1=1;
}else if ('0'<=s[i]&&s[i]<='9'){
if (phlag==0){
num1*=10;
num1+=s[i]-'0';
}else if (phlag==1){
num2*=10;
num2+=s[i]-'0';
}else{
num3*=10;
num3+=s[i]-'0';
}
}else if (s[i]=='?'){
if (phlag==0){
if (z1==0&&num1==0){
if (!(s[i+1]=='+'||s[i+1]=='-'||s[i+1]=='*')) z1=1;
}
num1*=10;
num1+=d;
}else if (phlag==1){
if (z2==0&&num2==0){
if (s[i+1]!='=') z2=1;
}
num2*=10;
num2+=d;
}else{
if (z3==0&&num3==0){
if ((i!=n-1)) z3=1;
}
num3*=10;
num3+=d;
}
}else if (phlag==1&&s[i]=='-'){
f2=1;
}else if (phlag==2&&s[i]=='-'){
f3=1;
}else if (s[i]=='='){
phlag=2;
}else{
if (s[i]=='+') type=0;
else if (s[i]=='-') type=1;
else if (s[i]=='*') type=2;
phlag=1;
}
}
if (f1==1) num1*=-1;
if (f2==1) num2*=-1;
if (f3==1) num3*=-1;
if (d==0&&(z1||z2||z3)) continue;
if (type==0){
if (num1+num2==num3){
cout << d << '\n';
return;
}
}else if (type==1){
if (num1-num2==num3){
cout << d << '\n';
return;
}
}else{
if (num1*num2==num3){
cout << d << '\n';
return;
}
}
}
cout << -1 << '\n';
return;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--) solve();
}
```
:::
### B. Alchemy
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### C. Containment
---
#### 題目摘要
10\*10\*10的方形內有一些壞點，求用最少的1\*1板子將壞點包住，好點包進來沒差
#### 想法
最小割。建模方式是將源點連到最外層的所有面，意思是如果是角落的點就連流量為3的邊，邊上的點就連流量為2，完全在面上的就連流量1，然後把壞點全部連流量無限大的邊到匯點。再將好點與他所有相鄰的點連流量為1的邊。
最大流就是將好點與壞點割開的最小割花費
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 1e6 + 5, IINF = 1e9 + 7;
const ll LINF = 1e18 + 5;
struct Dinic {
struct edge {
int v, r; ll rc;
};
vector<vector<edge>> adj;
vector<int> dis, it;
Dinic(int n) : adj(n), dis(n), it(n) {}
void add_edge(int u, int v, ll c) {
adj[u].pb({v, adj[v].size(), c});
adj[v].pb({u, adj[u].size() - 1, 0});
}
bool bfs(int s, int t) {
fill(all(dis), IINF);
queue<int> q;
q.push(s);
dis[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& [v, r, rc] : adj[u]) {
if (dis[v] < IINF || rc == 0) continue;
dis[v] = dis[u] + 1;
q.push(v);
}
}
return dis[t] < IINF;
}
ll dfs(int u, int t, ll cap) {
if (u == t || cap == 0) return cap;
for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
auto &[v, r, rc] = adj[u][i];
if (dis[v] != dis[u] + 1) continue;
ll tmp = dfs(v, t, min(cap, rc));
if (tmp > 0) {
rc -= tmp;
adj[v][r].rc += tmp;
return tmp;
}
}
return 0;
}
ll flow(int s, int t) {
ll ans = 0, tmp;
while (bfs(s, t)) {
fill(all(it), 0);
while ((tmp = dfs(s, t, IINF)) > 0) {
ans += tmp;
}
}
return ans;
}
bool inScut(int u) { return dis[u] < IINF; }
};
int enc(int i, int j, int k) {
return i * 100 + j * 10 + k;
}
void solve() {
int n; cin >> n;
vector bad(10, vector<vector<int>>(10, vector<int>(10, 0)));
rep (i, 0, n) {
int x, y, z; cin >> x >> y >> z;
bad[x][y][z] = 1;
}
Dinic G(1000 + 2);
int s = 1000, t = s + 1;
rep (i, 0, 10) rep (j, 0, 10) rep (k, 0, 10) {
int cnt = 0;
cnt += (i == 0 || i == 9) + (j == 0 || j == 9) + (k == 0 || k == 9);
if (cnt) G.add_edge(s, enc(i, j, k), cnt);
if (bad[i][j][k]) G.add_edge(enc(i, j, k), t, IINF);
else {
if (i) G.add_edge(enc(i, j, k), enc(i - 1, j, k), 1);
if (i != 9) G.add_edge(enc(i, j, k), enc(i + 1, j, k), 1);
if (j) G.add_edge(enc(i, j, k), enc(i, j - 1, k), 1);
if (j != 9) G.add_edge(enc(i, j, k), enc(i, j + 1, k), 1);
if (k) G.add_edge(enc(i, j, k), enc(i, j, k - 1), 1);
if (k != 9) G.add_edge(enc(i, j, k), enc(i, j, k + 1), 1);
}
}
cout << G.flow(s, t) << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t = 1;
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### D. Function
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### E. Hill Number
---
#### 題目摘要
求有多少小於$n$的山坡數，且$n$亦為山坡數
#### 想法
數位dp，dp[位數][數字(0到9)][下降過了沒][是否目前枚舉的每一位都貼在上界上]
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
ull dp[75][15][2][2];
void solve() {
string s;
cin >> s;
reverse(all(s));
while (s.size() > 1 && s.back() == '0') s.pop_back();
reverse(all(s));
int n=s.size();
s='$'+s;
for(int i=0;i<=n+1;i++) for(int d=0;d<10;d++) dp[i][d][0][0]=dp[i][d][0][1]=dp[i][d][1][0]=dp[i][d][1][1]=0;
dp[0][0][0][1]=1;
for(int i=1;i<=n;i++) for(int d=0;d<10;d++) for(int f=0;f<2;f++){
for(int k=0;k<10;k++){
if (f==1&&(d>(s[i]-'0'))) break;
if (k<=d) dp[i][d][0][f&&(d==(s[i]-'0'))]+=dp[i-1][k][0][f];
else dp[i][d][1][f&&(d==(s[i]-'0'))]+=dp[i-1][k][0][f];
if (k>=d) dp[i][d][1][f&&(d==(s[i]-'0'))]+=dp[i-1][k][1][f];
}
}
ull ans=0;
int phlag=0;
for(int i=1;i<=n;i++){
if (phlag==0&&s[i]<s[i-1]) phlag=1;
if (phlag==1&&s[i]>s[i-1]) phlag=2;
}
for(int d=0;d<10;d++) for(int x=0;x<2;x++){
ans+=dp[n][d][x][0];
}
if (phlag>1){
cout << -1 << '\n';
}else{
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### F. Knights
---
#### 題目摘要
$M\times N$的矩陣放騎士兩兩不攻擊的方法數
#### 想法
$N$超大，$M$超小，用矩陣快速冪。被攻擊到的格子只會跟上兩層有關，因此狀態只要記前兩層的狀態就好(最多$2^8$個)，接下來做一層的轉移到下一層就好
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
const ll MOD=1e9+9;
struct matrix{
ll m[260][260];
void init(int t){
for(int i=0;i<256;i++) for(int j=0;j<256;j++) m[i][j]=0;
for(int i=0;i<256;i++) m[i][i]=t;
}
};
matrix RES;
matrix mul(matrix a, matrix tmp){
RES.init(0);
for(int i=0;i<256;i++) for(int j=0;j<256;j++) for(int k=0;k<256;k++){
RES.m[i][j]+=a.m[i][k]*tmp.m[k][j]%MOD;
RES.m[i][j]%=MOD;
}
return RES;
}
matrix mpow(matrix x, int k){
matrix res;
res.init(1);
while(k){
if (k&1){
res=mul(res, x);
}
x=mul(x, x);
k>>=1;
}
return res;
}
ll fpow(ll x, int k){
ll res=1;
while(k){
if (k&1) res=res*x%MOD;
x=x*x%MOD;
k>>=1;
}
return res;
}
int moves[4][2]={{2, 1}, {-2, 1}, {1, 2}, {-1, 2}};
matrix mat;
int n, m;
void check(int s){
vector<vector<int>> v(n, vector<int>(3, 0));
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
int idx=j*n+i;
v[i][j]=(s>>idx)&1;
if (v[i][j]==0) continue;
for(int k=0;k<4;k++){
int ni=i+moves[k][0];
int nj=j+moves[k][1];
if (0<=ni&&ni<n&&nj==2){
v[ni][nj]=1;
}
}
}
}
int t=0;
for(int i=0;i<n;i++) t|=v[i][1]<<i;
for(int i=0;i<(1<<n);i++){
bool phlag=1;
for(int j=0;j<n;j++){
if (v[j][2]==1&&(i>>j&1)) phlag=0;
}
if (!phlag) continue;
mat.m[t|(i<<n)][s]=1;
}
}
void solve() {
cin >> n >> m;
if (n==1){
cout << fpow(2, m) << '\n';
}else{
mat.init(0);
for(int s=0;s<(1<<(2*n));s++) check(s);
mat=mpow(mat, m);
ll ans=0;
for(int i=0;i<(1<<(2*n));i++){
ans+=mat.m[i][0];
ans%=MOD;
}
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### G. Number Game
---
#### 題目摘要
A和B玩遊戲，給一個長度為$N$的permutation，A先手，輪流取出一個左右相鄰沒有比現在要取的東西還大的數字，取出來那格就變空的，先取出1的就贏了，求雙方都執行最佳策略的情況下誰會贏
#### 想法
先不管1在邊界的狀況，分為兩種case：1兩側的東西旁邊是否都沒有比他們更高的
仔細思考一下會發現，若是有至少一個更高的話最後肯定會將所有數字都取完，因此用$N$的奇偶判輸贏即可。否則由於會發現若先取的1左邊的那個，那麼1右邊的右邊一段連續往下的點都不可能會被取到，反之亦然。設因此看對於先手來說N減去左邊一串下降或者右邊一串連續下降的是不是對於自己好的奇偶，是的話就是先手贏，否則是後手。
對於在邊界的case就看單邊並用上面的標準判斷就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 1e6 + 5;
const ll LINF = 1e18 + 5;
void solve() {
int n; cin >> n;
vector<int> a(n);
int one = 0;
rep (i, 0, n) {
cin >> a[i];
if (a[i] == 1) one = i;
}
auto out = [&](int x) -> void {
cout << (x & 1 ? "Alice\n" : "Bob\n");
};
if (n <= 2) {
out(n);
return;
}
if (one == n - 1) {
rep (i, 0, n / 2) swap(a[i], a[n - 1 - i]);
one = 0;
}
if (one == 0) {
if (a[1] < a[2]) {
out(n);
return;
}
int ptr = 1;
while (ptr + 1 < n && a[ptr + 1] < a[ptr]) {
ptr++;
}
int tot = n - ptr + 1;
out(tot);
} else {
bool f = (one - 1 == 0 || a[one - 1] > a[one - 2]), f2 = (one + 1 == n - 1 || a[one + 1] > a[one + 2]);
if (f && f2) {
{
int ptr = one + 1;
while (ptr + 1 < n && a[ptr + 1] < a[ptr]) {
ptr++;
}
int tot = n - (ptr - one) + 1;
if (tot & 1) {
out(tot);
return;
}
}
{
int ptr = one - 1;
while (ptr - 1 >= 0 && a[ptr - 1] < a[ptr]) {
ptr--;
}
int tot = n - (one - ptr) + 1;
if (tot & 1) {
out(tot);
return;
}
}
out(2);
} else {
out(n);
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
// cout << i << '\n';
solve();
}
}
```
:::
### H. Pushups
---
#### 題目摘要
有陣列$S$，輸出一個陣列$A$的所有元素和，並$A$滿足所有元素都是$S$的元素，且所有前綴和的和為$N$
#### 想法
假設$A$的大小為$n$，那前綴和的和為$\sum_\limits{i=1}^{n}\sum_\limits{j=1}^{i}A_j$，並且這可以拆成$\sum_\limits{i=1}^{n}(n-i+1)\times A_i$。建一個$dp_{i,\ j}$為目前放到$A放i$個元素並滿足前綴和的和是$j$的最大元素和，因此這要再枚舉第$i$位時再枚舉第$i$位要放$S$的哪個元素就好，剩下的就和背包蠻像的
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
const int INF=1e9+7;
void solve() {
int n, m;
cin >> n >> m;
vector<int> v(m);
for(auto &x:v) cin >> x;
vector<int> dp(n+1, -INF);
dp[0]=0;
int ans=-1;
for(int i=1;i<=n;i++){
vector<int> tmp(n+1, -INF);
for(int j=0;j<m;j++){
int w=i*v[j];
for(int k=w;k<=n;k++){
tmp[k]=max(tmp[k], dp[k-w]+v[j]);
}
}
dp.swap(tmp);
if (dp[n]>=0) ans=max(ans, dp[n]);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### I. Salary Inequity
---
#### 題目摘要
給一顆樹，兩種操作
1. 子樹加值
2. 詢問子樹最大減最小
#### 想法
樹壓平+線段樹
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 1e6 + 5;
const ll LINF = 1e18 + 5;
ll s[MAXN], who[MAXN];
struct info {
ll mx, mi, tag;
void update(int);
} tree[MAXN << 2];
info operator+(info a, info b) {
return {max(a.mx, b.mx), min(a.mi, b.mi), 0};
}
void info::update(int val) {
mx += val;
mi += val;
tag += val;
}
void build(int pos, int l, int r) {
if (l == r) {
tree[pos] = {s[who[l]], s[who[l]], 0};
return;
}
int mid = l + r >> 1;
build(lpos, l, mid);
build(rpos, mid + 1, r);
tree[pos] = tree[lpos] + tree[rpos];
}
void push(int pos) {
if (tree[pos].tag) {
tree[lpos].update(tree[pos].tag);
tree[rpos].update(tree[pos].tag);
tree[pos].tag = 0;
}
}
void mod(int pos, int l, int r, int ml, int mr, int val) {
if (ml <= l && mr >= r) {
tree[pos].update(val);
return;
}
int mid = l + r >> 1;
push(pos);
if (ml <= mid) mod(lpos, l, mid, ml, mr, val);
if (mr > mid) mod(rpos, mid + 1, r, ml, mr, val);
tree[pos] = tree[lpos] + tree[rpos];
}
info query(int pos, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return tree[pos];
int mid = l + r >> 1;
push(pos);
info res = {0, LINF, 0};
if (ql <= mid) res = res + query(lpos, l, mid, ql, qr);
if (qr > mid) res = res + query(rpos, mid + 1, r, ql, qr);
return res;
}
void solve() {
int n; cin >> n;
vector<int> in(n + 1), out(n + 1);
vector<vector<int>> adj(n + 1);
rep (i, 2, n + 1) {
int p; cin >> p;
adj[p].pb(i);
adj[i].pb(p);
}
rep (i, 1, n + 1) cin >> s[i];
int id = 0;
auto dfs = [&](auto self, int u, int pa) -> void {
in[u] = ++id;
who[id] = u;
for (int v : adj[u]) {
if (v == pa) continue;
self(self, v, u);
}
out[u] = id;
};
dfs(dfs, 1, -1);
build(1, 1, n);
int q; cin >> q;
while (q--) {
char c; cin >> c;
if (c == 'Q') {
int x; cin >> x;
auto ans = query(1, 1, n, in[x], out[x]);
cout << ans.mx - ans.mi << '\n';
} else {
int p, v; cin >> p >> v;
mod(1, 1, n, in[p], out[p], v);
}
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### J. Stamp Stamp
---
#### 題目摘要
#### 想法
:::spoiler 實作
```cpp=
```
:::
### K. Towers
---
#### 題目摘要
請構造大小為$N\times N$的方格，裡面要像數獨一樣行列要1-n，若有給定的數字要照填，並且要符合給某些方向看過去從小到大能看到多少數字
$3\le N\le 5$
#### 想法
觀察到他超小，然後實際上可行的組合應該不會太多，實測5\*5合法的所有盤面數量級1e5。因此預處理好所有可行的盤面，再一一檢查是否符合條件就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define ull unsigned long long
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1
const int MAXN = 1e6 + 5;
const ll LINF = 1e18 + 5;
int tmp[5][5], cnt[3];
int G[3][161285][5][5];
void dfs(int k, int id) {
if (id == k * k) {
rep (i, 0, k) rep (j, 0, k) {
G[k - 3][cnt[k - 3]][i][j] = tmp[i][j];
}
cnt[k - 3]++;
return;
}
int x = id / k, y = id % k;
rep (i, 1, k + 1) {
bool f = 0;
rep (j, 0, x) if (tmp[j][y] == i) {
f = 1;
break;
}
if (f) continue;
rep (j, 0, y) if (tmp[x][j] == i) {
f = 1;
break;
}
if (f) continue;
tmp[x][y] = i;
dfs(k, id + 1);
tmp[x][y] = 0;
}
}
void solve() {
int n; cin >> n;
vector<string> g(n + 2);
rep (i, 0, n + 2) cin >> g[i];
auto check = [&](int id) -> bool {
rep (i, 0, n) rep (j, 0, n) if (g[i + 1][j + 1] != '-') {
if (g[i + 1][j + 1] - '0' != G[n - 3][id][i][j]) return false;
}
rep (i, 1, n + 1) {
if (g[0][i] != '-') {
int vis = 1, mx = G[n - 3][id][0][i - 1];
rep (j, 1, n) {
vis += G[n - 3][id][j][i - 1] > mx;
mx = max(mx, G[n - 3][id][j][i - 1]);
}
if (vis != g[0][i] - '0') return false;
}
if (g[n + 1][i] != '-') {
int vis = 1, mx = G[n - 3][id][n - 1][i - 1];
for (int j = n - 2; j >= 0; --j) {
vis += G[n - 3][id][j][i - 1] > mx;
mx = max(mx, G[n - 3][id][j][i - 1]);
}
if (vis != g[n + 1][i] - '0') return false;
}
if (g[i][0] != '-') {
int vis = 1, mx = G[n - 3][id][i - 1][0];
rep (j, 1, n) {
vis += G[n - 3][id][i - 1][j] > mx;
mx = max(mx, G[n - 3][id][i - 1][j]);
}
if (vis != g[i][0] - '0') return false;
}
if (g[i][n + 1] != '-') {
int vis = 1, mx = G[n - 3][id][i - 1][n - 1];
for (int j = n - 2; j >= 0; --j) {
vis += G[n - 3][id][i - 1][j] > mx;
mx = max(mx, G[n - 3][id][i - 1][j]);
}
if (vis != g[i][n + 1] - '0') return false;
}
}
return true;
};
rep (k, 0, cnt[n - 3]) {
if (check(k)) {
rep (i, 0, n) {
rep (j, 0, n) cout << G[n - 3][k][i][j];
cout << '\n';
}
cout << '\n';
return;
}
}
cout << "no\n";
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t = 1;
rep (i, 3, 6) dfs(i, 0);
cin >> t;
rep (i, 1, t + 1) {
solve();
}
}
```
:::
### L. Wormhole
---
#### 題目摘要
給超少點，三維空間，有m個有向蟲洞讓兩個點間的距離是0，其他是歐氏幾何距離，q筆詢問求兩點間最短路
#### 想法
超水題，但輸出要round超爛，做個floyd-warshall就結束了。
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
const ll LINF = 5e18 + 5;
ll sq(ll x) {
return x * x;
}
void solve() {
int n; cin >> n;
vector<string> s(n);
map<string, vector<int>> id;
vector<ll> x(n), y(n), z(n);
rep (i, 0, n) {
cin >> s[i];
id[s[i]].pb(i);
cin >> x[i] >> y[i] >> z[i];
}
int m; cin >> m;
vector w(n, vector<long double>(n, 0));
auto dis = [&](int i, int j) -> long double {
return sqrtl(sq(x[i] - x[j]) + sq(y[i] - y[j]) + sq(z[i] - z[j]));
};
rep (i, 0, n) rep (j, 0, n) w[i][j] = dis(i, j);
rep (i, 0, m) {
string a, b; cin >> a >> b;
for (int u : id[a]) for (int v : id[b]) w[u][v] = 0;
}
rep (k, 0, n) rep (i, 0, n) rep (j, 0, n) {
w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}
int q; cin >> q;
while (q--) {
string a, b; cin >> a >> b;
long double mi = LINF;
for (int u : id[a]) for (int v : id[b]) mi = min(mi, w[u][v]);
cout << "The distance from " << a << " to " << b << " is ";
cout << (ll)(mi+0.5) << ' ';
cout << "parsecs.\n";
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
rep (i, 1, t + 1) {
cout << "Case " << i << ":\n";
solve();
}
}
```
:::
Sign in with Wallet
Connect another wallet