QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#386184#7455. stcmoscaryangWA 73ms8848kbC++171.9kb2024-04-11 13:46:212024-04-11 13:46:22

Judging History

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

  • [2024-04-11 13:46:22]
  • 评测
  • 测评结果:WA
  • 用时:73ms
  • 内存:8848kb
  • [2024-04-11 13:46:21]
  • 提交

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