QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#74725#5002. Distance and TreeSmallbasic#ML 2ms5472kbC++141.3kb2023-02-03 15:45:372023-02-03 15:45:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-03 15:45:38]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:5472kb
  • [2023-02-03 15:45:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

int n, d[N], fr[N], to[N], top = 0;

inline void addedge(int from, int t) {
	fr[++top] = from; to[top] = t;
}

inline int abs_(int a) {
	return a < 0 ? -a : a;
}

inline bool calc(int L, vector<int> p) {
	vector<int> q; int t = -1;
	bool res = 1;
	for (int i : p) {
		if (d[i] == d[L] + 1) {
			addedge(L, i); t = i;
			if (!q.empty()) {
				res &= calc(i, q);
				if (!res) return 0;
			}
			q.clear();
		} else q.push_back(i);
	} if (!q.empty()) {
		if (t == -1) return 0;
		return calc(t, q);
	} return 1;
}

int main() {
	n = read();
	for (int i = 1; i <= n; ++i) d[i] = read();
	int rt = 0;
	for (int i = 1; i <= n; ++i) {
		if (!d[i]) rt = i;
	}
	if (!rt) puts("-1");
	else {
		vector<int> p;
		for (int i = rt + 1; i <= n; ++i)
			p.push_back(i);
		for (int i = 1; i < rt; ++i)
			p.push_back(i);
		if (!calc(rt, p)) puts("-1");
		else {
			for (int i = 1; i < n; ++i)
				printf("%d %d\n", fr[i], to[i]);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5328kb

input:

5
0 1 2 1 3

output:

-1

result:

ok Accepted

Test #2:

score: 0
Accepted
time: 2ms
memory: 5472kb

input:

5
1 1 0 1 1

output:

3 4
3 5
3 1
3 2

result:

ok Accepted

Test #3:

score: -100
Memory Limit Exceeded

input:

100000
96770 96764 96762 96761 96759 96755 96754 96753 96752 96751 96750 96748 96746 96745 96741 96740 96739 96736 96735 96734 96730 96728 96727 96726 96723 96718 96714 96712 96710 96709 96706 96705 96704 96703 96702 96698 96697 96696 96695 96693 96692 96690 96687 96684 96683 96682 96681 96679 96677...

output:


result: