QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51582#3876. Attack on Alpha-ZetopokWA 27ms144264kbC++2.7kb2022-10-02 19:48:382022-10-02 19:48:40

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-02 19:48:40]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:144264kb
  • [2022-10-02 19:48:38]
  • 提交

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: 27ms
memory: 144264kb

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 '