QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386184 | #7455. stcm | oscaryang | WA | 73ms | 8848kb | C++17 | 1.9kb | 2024-04-11 13:46:21 | 2024-04-11 13:46:22 |
Judging History
answer
#include<bits/stdc++.h>
#define vc vector
#define pb emplace_back
#define pii pair <int, int>
#define mkp make_pair
#define tup tuple <int, int, int>
#define mkt make_tuple
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
mt19937 gen(time(0));
inline int read() {
int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}
const int N = 1e5 + 5;
int n, fa[N], le[N], ri[N], idf[N], DFN;
vc <int> G[N];
inline void dfs (int x) {
le[x] = ++DFN; idf[DFN] = x;
for (auto y : G[x]) dfs (y);
ri[x] = DFN;
}
inline void out (int x) { putchar ('='); printf ("%d", x); }
inline void add (int x) { putchar ('+'); printf ("%d", x); }
inline void del () { putchar ('-'); }
inline void binary (int L, int R, vc <tup> a) {
if(L == R) {
auto [l, r, id] = a[0];
out (id); del (); return ;
}
int mid = L + R >> 1;
vc <tup> le, ri; int cnt = 0, i = L, j = R;
for (auto [l, r, id] : a)
if(l <= mid && r > mid) {
while (i < l) add (idf[i++]), ++cnt;
while (j > r) add (idf[j--]), ++cnt;
out (id);
}
else if(r <= mid) le.pb (mkt(l, r, id));
else ri.pb (mkt(l, r, id));
while (cnt--) del ();
if (le.size()) {
rep (i, mid + 1, R) add (idf[i]);
binary (L, mid, le);
rep (i, mid + 1, R) del ();
}
if (ri.size()) {
rep (i, L, mid) add (idf[i]);
binary (mid + 1, R, ri);
rep (i, L, mid) del ();
}
}
inline void testcase () {
rep (i, 1, n) fa[i] = le[i] = ri[i] = 0, G[i].clear (); DFN = 0;
rep (i, 2, n) G[fa[i] = read()].pb (i);
dfs (1);
vc <tup> seg;
rep (i, 1, n) seg.pb (mkt(le[i], ri[i], i));
sort (seg.begin (), seg.end ());
binary (1, n, seg);
putchar ('!'); putchar (10);
}
signed main() {
while (scanf ("%d", &n) != EOF) testcase ();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 73ms
memory: 8848kb
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+772+569+940+882+812+494+243+968+773+732+727+570+441+905+754+435+980+665+426+323+843+798+622+412+206+177+619+590+175+994+778+129+873+691+650+523+468+136+73+531+195+60+53+661+548+368+983+837+319+601+421+362+342+696+678+481+291+202+874+649+521+764+247+663+598+347+346+936+400+290+192+167+473+745+40...
result:
wrong answer -1 / -1 / -1