QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413548 | #7455. stcm | james1BadCreeper | WA | 114ms | 9804kb | C++14 | 2.2kb | 2024-05-17 18:24:31 | 2024-05-17 18:24:33 |
Judging History
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) {
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]
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: 114ms
memory: 9804kb
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