QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413553#7455. stcmjames1BadCreeperWA 102ms9836kbC++142.2kb2024-05-17 18:27:382024-05-17 18:27:39

Judging History

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

  • [2024-05-17 18:27:39]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:9836kb
  • [2024-05-17 18:27:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5; 

int n, sz[N], dfn[N], num, idx[N]; 
int fa[N]; 
vector<int> G[N]; 
struct Query {
    int l, r, id; 
    Query(int l = 0, int r = 0, int id = 0) : l(l), r(r), id(id) {}
    bool operator< (const Query &a) const {
        return l < a.l; 
    }
}; 
vector<Query> Q; 

void dfs(int x, int ff) {
    sz[x] = 1; idx[dfn[x] = ++num] = x; 
    for (int y : G[x]) if (y != ff) dfs(y, x), sz[x] += sz[y]; 
    Q.emplace_back(dfn[x], dfn[x] + sz[x] - 1, x); 
} 

void solve(vector<Query> Q, int l, int r) {
    if (l == r) {
        assert(Q.size() <= 1); 
        if (Q.size()) cout << "=" << Q[0].id; 
        return; 
    }
    int mid = l + r >> 1; 

    vector<Query> lt, rt, now; 
    for (auto it : Q)
        if (it.r < mid) lt.emplace_back(it); 
        else if (it.l > mid) rt.emplace_back(it); 
        else now.push_back(it); 

    // 当前已经加入 [1, l - 1], [r + 1, n]
    int pl = l, pr = r, cnt = 0; 
    for (auto it : now) {
        // [l, r] 
        assert(it.l >= l); assert(it.r <= r); 
        while (pl < it.l) cout << "+" << pl++, ++cnt; 
        while (pr > it.r) cout << "+" << pr--, ++cnt; 
        cout << "=" << it.id; 
    }
    for (int i = 1; i <= cnt; ++i) cout << "-"; 
    // exit(0); 

    if (l <= mid - 1 && lt.size()) {
        for (int i = r; i >= mid; --i) cout << "+" << i;  
        solve(lt, l, mid - 1); 
        for (int i = r; i >= mid; --i) cout << "-"; 
    }

    if (mid + 1 <= r && rt.size()) {
        for (int i = l; i <= mid; ++i) cout << "+" << i; 
        solve(rt, mid + 1, r); 
        for (int i = l; i <= mid; ++i) cout << "-"; 
    }
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0); 
    while (cin >> n) {
        num = 0; 
        for (int i = 2; i <= n; ++i) cin >> fa[i]; 
        for (int i = 1; i <= n; ++i) G[i].clear(); 
        for (int i = 2; i <= n; ++i)
            G[fa[i]].emplace_back(i), 
            G[i].emplace_back(fa[i]); 
        Q.clear(); 
        dfs(1, 0); 
        sort(Q.begin(), Q.end()); 

        // for (auto it : Q) cout << it.l << " " << it.r << " " << it.id << "\n"; 

        solve(Q, 1, n); 
        cout << "!\n"; 
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 102ms
memory: 9836kb

input:

1000
1 1 2 1 1 2 2 7 2 7 3 11 10 6 4 8 10 13 16 2 19 7 6 18 6 2 16 27 21 14 6 14 14 29 12 13 3 27 28 27 2 34 26 27 44 14 30 25 7 50 47 1 36 24 4 32 10 20 53 52 61 23 43 39 2 15 47 9 14 54 48 53 36 14 14 66 76 55 17 67 21 22 18 25 67 75 7 48 21 6 35 11 31 41 63 28 6 98 51 3 29 52 102 77 27 58 39 64 9...

output:

=1+1+1000+999+998+997+996+995+994+993+992+991+990+989+988+987+986+985+984+983+982+981+980+979+978+977+976+975+974+973+972+971+970+969+968+967+966+965+964+963+962+961+960+959+958+957+956+955+954+953+952+951+950+949+948+947+946+945+944+943+942+941+940+939+938+937+936+935+934+933+932+931+930+929+928+92...

result:

wrong answer -1 / -1 / 801727