QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51583 | #3876. Attack on Alpha-Zet | opok | WA | 19ms | 144352kb | C++ | 2.7kb | 2022-10-02 19:49:08 | 2022-10-02 19:49:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 1e6;
const int L = 30;
vi adj[mx+1];
int depth[mx+1], par[mx+1][L];
void dfs (int u) {
for (int v : adj[u]) {
if (v==par[u][0]) continue;
depth[v] = depth[u]+1;
par[v][0] = u;
dfs (v);
}
}
int go_up (int x, int d) {
rep (i,0,L-1) {
if (d%2) x = par[x][i];
d /= 2;
}
return x;
}
int lca (int a, int b) {
if (depth[a]<depth[b]) swap(a,b);
int dif = depth[a]-depth[b];
a = go_up (a, dif);
if (a==b) return a;
rrep (i, L-1, 0) {
if (par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
memset(par, -1, sizeof(par));
int h, w; cin >> h >> w;
string trash;
getline(cin, trash);
rep (i,0,h) {
string s;
getline(cin, s);
if (i==0) continue;
rep (j,0,2*w) {
char c = s[j];
if (j%2==1) {
if (c==' ') {
int x = (i-1)*w+(j-1)/2;
adj[x].pb(x+w);
adj[x+w].pb(x);
}
}
if (j%2==0) {
if (c==' ') {
int x = (i-1)*w+j/2;
adj[x].pb(x-1);
adj[x-1].pb(x);
}
}
}
}
rep (i,0,h*w-1) {
cout << i << ": ";
for (int v : adj[i]) {
cout << v << " ";
}
cout << endl;
}
par[0][0] = 0;
dfs (0);
rep (i,1,29) {
rep (j,0,h*w-1) {
par[j][i] = par[par[j][i-1]][i-1];
}
}
int m, p = -1; cin >> m;
ll ans = 0;
rep (i,1,m) {
int x, y; cin >> x >> y;
x--, y--;
ll cur = x*w+y;
if (i>1) {
ans = (ans + depth[cur]+depth[p]-depth[lca(cur,p)]);
}
p = cur;
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 19ms
memory: 144352kb
input:
2 6 _ _ _ _ _ _ | _ _ _ _ _| |_ _ _ _ _ _| 5 1 5 1 1 1 6 1 1 1 5
output:
0: 6 1 1: 0 2 2: 1 3 3: 2 4 4: 3 5 5: 4 6: 0 7 7: 6 8 8: 7 9 9: 8 10 10: 9 11 11: 10 18
result:
wrong answer 1st lines differ - expected: '18', found: '0: 6 1 '